Codeforces #181 Div2 E "Empire Strikes Back"
問題
http://codeforces.com/contest/300/problem/E
訳
はるか遠い銀河系において、再び戦争が起きていた。
反乱国はそれぞれパワーがa_iの、k基の高性能ミサイルを保有している。
この脅威に対抗するために、連合国最高評議会は、
反乱国に決定的な打撃を与える事を決めた。
紛争の完結を成功させるためには、打撃を与えた後の対立バランスが、
正の整数となっていなければならない。
対立バランスは次のような数値である。
対立バランス = p / q p = n! ( n は打撃に使用するコストである) q = a_1! * a_2! * ... * a_k!
長年の戦争の末、連合国の資源はとても少なくなっている。
対立バランスを正の整数にするための、最小の打撃のコストnを出力せよ。
制約
1 <= k <= 10^6
1 <= a_i <= 10^7
考えた事
pを素因数分解したもの 2^a * 3^b * 5^c * 7^d...
qを素因数分解したもの 2^a * 3^b * 5^c * 7^d...
があるとして、
pのa, b, c, d,... が、qのそれを全てにおいて同じか上回っていなければ、
p / qは整数にならない。
ACしてるソースコードをカンニング
まずはqを素因数分解
まずq = a_1! * a_2!... * a_k!を2^a * 3^b * 5^c * 7^d...へ素因数分解する。
それにはまず入力でn!の数を取得した後、
1~10^7の各数値が何度掛けられているかを出す。
その後、あらかじめ出しておいた1~10^7の各数値の最大素因数で、
割っていっていくことで素因数分解ができる。
(こんなやり方があったのか・・・)
素因数分解ができたら、各素因数の指数(a, b, c, d...)を上回るための、
最小のn!をだして、その最大値をとっていく。
最小のn!を素早くだす
ただし、最大の入力( k = 10^6 a_i = 10^7 )がくると、
qの2の指数は1000億程になり、
それに達するには1000億!程必要になる(当社調べ)
愚直に計算できないので、以下のような性質を利用する。
n!を素因数分解したとき、素数xの指数をrとすると、
r * ( x - 1 ) < nで、r * ( x - 1 ) と n はかなり近い。
例えば、8!には2^7が含まれており、
7 * ( 2 - 1 ) = 7 < 8で、7と8はかなり近い。
12!には3^5が含まれており、
5 * ( 3 - 1 ) = 10 < 12で、10と12はかなり近い。
素因数2の時
n! | 2 | 4 | 6 | 8 | 10 | 12 | 14 | 16 | 18 | 20 | 22 | 24 | 26 |
r追加分 | 1 | 2 | 1 | 3 | 1 | 2 | 1 | 4 | 1 | 2 | 1 | 3 | 1 |
r合計 | 1 | 3 | 4 | 7 | 8 | 10 | 11 | 15 | 16 | 18 | 19 | 22 | 23 |
r*(2-1) | 1 | 3 | 4 | 7 | 8 | 10 | 11 | 15 | 16 | 18 | 19 | 22 | 23 |
素因数3の時
n! | 3 | 6 | 9 | 12 | 15 | 18 | 21 | 24 | 27 | 30 | 33 | 36 | 39 |
r追加分 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | 1 | 3 | 1 | 1 | 2 | 1 |
r合計 | 1 | 2 | 4 | 5 | 6 | 8 | 9 | 10 | 13 | 14 | 15 | 17 | 18 |
r*(3-1) | 2 | 4 | 8 | 10 | 12 | 16 | 18 | 20 | 26 | 28 | 30 | 34 | 36 |
この性質を利用し、素数xが指数rを持つような最小のn!を求めるときに、
( r * (x - 1) )!から調べていけば、素早くにnを求められる。
例えば、3^4となるような最小のn!を求める時は
4 * (3 - 1) = 8となるので、
8!から調べていけば、スグに答えである9!が見つかる。
2分探索?
タグにもあるように2分探索で解決する方法もあるようです。
おそらく、nについて2分探索するんだとは思うけど・・
あとでやろ
ソースコード
int main(){ // fact[i] = 0 - iそれ自身が素数 それ以外 - iの一番大きな素因数 vector<int> fact(1e7+1); for (int i = 2; i <= 3162; ++i){ if (fact[i]) continue; for (int j = i*i; j <= 1e7; j += i){ fact[j] = i; } } int n, a; cin >> n; // n!の数をexpへ入力 vector<long long> exp(1e7+2); while (n--) { cin >> a; ++exp[a]; } // 1~10^7の掛けられた数を取得 for (int i = 1e7; i >= 2; --i){ exp[i] += exp[i+1]; } // 2^a * 3^b * 5^c * 7^d... と素因数分解する for (int i = 1e7; i >= 2; --i) { if (fact[i]) { exp[fact[i]] += exp[i]; exp[i/fact[i]] += exp[i]; exp[i] = 0; } } // 各素因数に必要なn!をだして、最大値をとっていく long long ans = 1; for (int x = 2; x <= 1e7; ++x) { // 素因数が現在の答えで十分足りているならば戻る if (ans >= exp[x] * x ) continue; // n!のxの素因数をr個持つとすると、r * ( x - 1 ) < n である long long n = exp[x] * (x - 1) / x * x; long long r = 0; // n!をやったときに、素因数xをどのくらい持っているか計算 for (long long tmp = n / x; tmp > 0; tmp /= x){ r += tmp; } // 素因数xの指数が同じか超えるまで続ける while (r < exp[x]) { n += x; ++r; // 1増やしたから指数を足しますね。 // いやそれ本当はもっと足されるでしょ? for (long long tmp = n / x; tmp % x == 0; tmp /= x){ ++r; } } ans = max(ans, n); } // 出力 cout << ans << endl; return 0; }