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; }