[AtCoder] ABC 170 D – Not Divisible

2020年6月15日2020年12月14日

問題

方針

数列に \( 1 \) が含まれるとき、\( 1 \) の個数が \( 1 \) ならば、答えは \( 1 \) であり、複数あれば答えは \( 0 \) となります。次に、数列に \( 1 \) が含まれない場合を考えます。同じ値の要素は互いに割り切れるので、数列のセット \( s \) を考えます。ここで、\( s \) の要素の倍数を列挙します。倍数は \( 10^6 \) 以下のものを考えます。この計算量は、

\[ 10^6(1 + \dfrac{1}{2} + \cdots + \dfrac{1}{N})\]

以下なので、行うことができます。したがって、\( A_i \) が \( s \) の要素の倍数に含まれるかどうかを調べればよいです。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAX = 1000001;
int b[MAX]{};

int main() {
    int N;
    cin >> N;
    int A[N];
    set<int> s;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        b[A[i]]++;
        s.insert(A[i]);
    }
    bool flag[MAX]{};
    for (int i : s) {
        for (int j = 2; j < MAX; j++) {
            if (i * j >= MAX) break;
            flag[i * j] = true;
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (b[A[i]] == 1 && !flag[A[i]]) ans++; 
    }
    cout << ans << "\n";
    return 0;
}