Divisors [Lyft Level 5 Challenge 2018 - Elimination Round D]

http://codeforces.com/contest/1033/problem/D

N要素の配列Aがある。
各要素は必ず約数が3～5個になっている。
配列の要素の総積を取ったとき、これの約数の個数は何個か。

解法

http://codeforces.com/contest/1033/submission/43979011

約数の制約を言い換える。

• 約数が3つ→p^2
• 約数が4つ→pq or p^3
• 約数が5つ→p^4

※ p,qは素数
　
cnt[p] := 総積を取った時の素因数pの個数
pr := 総積に含まれる素因数
done[i] := 要素i番目の処理が終わったか
これを作りながら処理していこう
　
まずp^4とp^3は二分探索を使って、該当するpがあるか探っていこう。
makePrimes(i) := [2,i]の区間の素数を返す
自分の実装はエラトステネスの篩である。
これはそんなに難しくない。
　
次にp^2はsqrt関数を使おう。
単にA[i]が何かの平方数であるかを探している。
合成数^2を誤検知しそうだが、p^2q^2の構成はありえない、かつ、
p^4の場合は先に検知しているため、得られる平方根は素数である。
　
最後にpqが難しい。
これでdone[i] = 0である要素はpqになっていることが分かる。
普通に素因数分解するのは難しいので、p^4,p^3,p^2の処理の過程で得られた素数を使う。
他にも使える素数が実はあり、pqとなっている要素通しでgcdを使うと、共通の素因数が得られる場合がある。
全てのpqの要素のペアについてgcdをとり、共通の素因数gがあった場合はそれをprに記憶しておく。
共通の素因数が見つかれば、それで割った数が素因数として更に得られるのでそれもprに記憶しておく。
これで使える素数が出揃ったので、これを使ってpqを全て処理していこう。
　
これでもまだ未処理のpqが余る。
このpqに当てはまる条件は

• 素因数が処理済みの要素に含まれない
• 他の要素と素因数を共有しない　または　他の要素と全く同じ数である

cnt2[j] := 未処理のpqでA[i] = jであるiの個数
これで全く同じ数は1つにまとめておこう。
未知のpqがcnt2[i]個あるとする。
このとき、これを総積に含めると、pもqもcnt2[i]個追加される。
このp,qは他の要素に含まれないため、pとqはcnt2[i]個で確定になる。
よって、約数の個数的には×(cnt2[i] + 1)^2になる。
実際にp,qの数がわからなくても約数の個数的には問題がない。

int N; ll A[505];
ll mo = 998244353;
int done[505];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> A[i];

    map<ll, int> cnt;
    set<int> pr;
    
    // p^4
    auto vp4 = makePrimes(37607); // (2*10^18)^(1/4) = 37606.0309309
    rep(i, 0, N) if (!done[i]) {
        int ng = -1, ok = vp4.size() - 1;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;
            ll x = 1LL * vp4[md] * vp4[md] * vp4[md] * vp4[md];
            if (A[i] <= x) ok = md;
            else ng = md;
        }
        ll x = 1LL * vp4[ok] * vp4[ok] * vp4[ok] * vp4[ok];
        if (x == A[i]) {
            cnt[vp4[ok]] += 4;
            done[i] = 1;
            pr.insert(vp4[ok]);
        }
    }

    // p^3
    auto vp3 = makePrimes(1259922); // (2*10^18)^(1/3) = 1259921.04989
    rep(i, 0, N) if (!done[i]) {
        int ng = -1, ok = vp3.size() - 1;
        while (ng + 1 != ok) {
            int md = (ng + ok) / 2;
            ll x = 1LL * vp3[md] * vp3[md] * vp3[md];
            if (A[i] <= x) ok = md;
            else ng = md;
        }
        ll x = 1LL * vp3[ok] * vp3[ok] * vp3[ok];
        if (x == A[i]) {
            cnt[vp3[ok]] += 3;
            done[i] = 1;
            pr.insert(vp3[ok]);
        }
    }

    // p^2
    rep(i, 0, N) if (!done[i]) {
        ll d = (ll)sqrt(A[i]) - 1;
        while (d*d < A[i]) ++d;
        if (d * d == A[i]) {
            cnt[d] += 2;
            done[i] = 1;
            pr.insert(d);
        }
    }

    // 残りはpq
    rep(i, 0, N) rep(j, i + 1, N) if (!done[i] and !done[j] and A[i] != A[j]) {
        ll g = gcd(A[i], A[j]);
        if (1 < g) {
            pr.insert(g);
            pr.insert(A[i] / g);
            pr.insert(A[j] / g);
        }
    }

    rep(i, 0, N) fore(p, pr) if (A[i] % p == 0 and !done[i]) {
        cnt[p]++;
        cnt[A[i] / p]++;
        done[i] = 1;
    }

    ll ans = 1;

    // ans計算
    fore(p, cnt) ans = ans * (p.second + 1) % mo;

    // 処理されていないやつは、「他と素因数がかぶらない全て同じpq」or「他と素因数がかぶらない全て違うpq」
    map<ll, int> cnt2;
    rep(i, 0, N) if (!done[i]) cnt2[A[i]]++;
    fore(p, cnt2) ans = ans * (p.second + 1) * (p.second + 1) % mo;

    cout << ans << endl;
}