Submission #62815327

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    
    // 各数字の出現回数
    vector<int> c(mx + 1, 0);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    int mx = 0;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    
    // 各数字の出現回数
    vector<int> c(mx + 1, 0);
    for (int i = 0; i < n; i++){
        c[a[i]]++;
    }
    
    // cc[d] = 入力中の d の倍数の個数
    vector<int> cc(mx + 1, 0);
    for (int d = 1; d <= mx; d++){
        for (int j = d; j <= mx; j += d){
            cc[d] += c[j];
        }
    }
    
    // mxまでの最小素因数を求める（ふるい）
    vector<int> sieve(mx + 1);
    for (int i = 0; i <= mx; i++){
        sieve[i] = i;
    }
    for (int p = 2; p * p <= mx; p++){
        if (sieve[p] == p) {
            for (int q = p * p; q <= mx; q += p){
                if (sieve[q] == q) {
                    sieve[q] = p;
                }
            }
        }
    }
    
    // 各数字について、条件を満たす最大の約数を出力
    for (int i = 0; i < n; i++){
        int x = a[i];
        vector<int> factors;
        // x の素因数分解（重複あり）
        while (x > 1) {
            factors.push_back(sieve[x]);
            x /= sieve[x];
        }
        
        // factors から全ての約数（重複を除く）を生成
        set<int> divs;
        int m = factors.size();
        for (int mask = 0; mask < (1 << m); mask++){
            int prod = 1;
            for (int j = 0; j < m; j++){
                if (mask & (1 << j))
                    prod *= factors[j];
            }
            divs.insert(prod);
        }
        
        // 降順にソート
        vector<int> dvec(divs.begin(), divs.end());
        sort(dvec.begin(), dvec.end(), greater<int>());
        
        int ans = 1;
        for (int d : dvec){
            if (cc[d] >= k){
                ans = d;
                break;
            }
        }
        cout << ans << "\n";
    }
    
    return 0;
}

Submission Info

Judge Result