WARush

SRMの結果とか、解けた問題のコードを書いていきます

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