A - Uncommon

A - Uncommon

xと互いに素なものを数える場合、xの約数について、それらの倍数の個数が全て分かれば
素因数の数をcとして、包除原理でO(2^c * c)で解ける

今回a1 ~ an <= 10^5なので、バケツを用意すれば1~Mまでの倍数の個数はO(N log N)で分かる
よって包除原理が使える
ここで<=10^5を素因数分解したとき、その数は高々6個である
よって、O(N * 2^6 * 6)で間に合う
Submission #3781369 - 「みんなのプロコン 2018」決勝

int a[k5];
int co[k5];
signed main() {
    cin >> N >> M;
    rep(i, N)a[in()]++;
    rep(i, 1, M + 1) {
        for (int j = i; j < k5; j += i) {
            co[i] += a[j];
        }
    }
    cout << N << endl;
    //co[i] := i と互いに素でないものの個数
    rep(i, 2, M + 1) {
        vi fac = factorization(i);
        int res = N;//引いてく
        int fsize = fac.size();
        rep(m, 1, 1 << fsize) {
            int mul = 1;
            rep(j, fsize) if (bget(m, j))mul *= fac[j];
            //奇数個なら引く
            if (bcou(m) % 2)res -= co[mul];
            else res += co[mul];
        }
        cout << res << endl;
    }
    return 0;
}