joi春合宿2007 day1-2:Factorial

問題文

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf

解法

頭悪いことしました(素因数分解+二分探索など)

まず、素因数分解します。これは、√Nくらいまでしかループを回さない素因数分解のテクを使うとO(√N)くらいでできます。

すると、Nの因数である素数たちについて、求める階乗の値に何回登場すればいいかがわかります。(例えばNが2^3の倍数だった場合は、求める階乗を素因数分解すると2が3個以上登場する)

ところで、ある整数Mがあるとして、1~Mをそれぞれ素因数分解するとある素数pが合計で何度登場するか知りたい場合は、Mをpでひたすら割ればよいですよね。例えば、1から8までの数字の素因数分解に2が何度登場するか知りたい場合は、8/2+8/4+8/8=7と計算して、7回登場すると分かります(2と6は1個、4は2個、8は3個、素因数分解に2が登場します。)。1~Mの整数があったら、M/2個は2の倍数。M/2個の整数の中で、(M/2)/2個はさらに2の倍数(つまり4の倍数)、…という感じです。

M!は当然1~Mを全部掛け合わせた値です。よって、M!を素因数分解したとき、ある素数pが登場する回数を求めたいときは、1~Mそれぞれの素因数分解にpが登場する回数の合計を求めればよいです。1~Mそれぞれの素因数分解に素数pが登場する回数の合計を求める方法はさっき書いた通りです。

ここで、例えば2が3回以上M!の素因数分解に登場するような最少のMが求めたくなります。落ち着いて考えると、「Mがx以上ならば2が必ず3回以上登場し、x未満ならば必ず3回以上登場しない」、というようなxがあるはずです。

3!の素因数分解には2は1度しか登場しません。ここで、2!の素因数分解で2が3つとか出てきたらおかしいですよね。つまり、ある整数yが条件を満たさなかったら、y-1も条件を満たさないわけです。逆にyが条件を満たせばy+1も条件を満たすはずです。こんな感じなんで境目が多分あります。

このような境目を効率的に出す二分探索という手法がありますね。
二分探索はO(logN)とかでできます。
結局、Nの素因数分解に登場した素数それぞれについて、二分探索で境目をだして、それらの最大値を出力すればACするわけです。
上記のような素数それぞれについて二分探索しても、結構大きく見積もってもO(NlogN)なので、きっと間に合います。

昔解こうとしたときはWAとTLEしか出なかったので、1step進化したのかもしれません。
来年くらいにO(N)とかでパパッと解くアルゴリズムを思いつけたらいいですね。

コード

#include<bits/stdc++.h>
using namespace std;

map<int,int>Cnt;

int C(int n,int m){
    int lb=1,ub=100000000;
    while(ub-lb>1){
        int mid=(lb+ub)/2;
        int sum=0;
        int latte=mid;
        while(latte){
            sum+=latte/n;
            latte/=n;
        }
        if(sum>=m)ub=mid;
        else lb=mid;
    }
    return ub;
}

int main(){
    int n;
    cin>>n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            while(n%i==0){
                Cnt[i]++;
                n/=i;
            }
        }
    }
    if(n!=1)Cnt[n]++;
    int ans=0;
    for(map<int,int>::iterator it=Cnt.begin();it!=Cnt.end();it++){
        ans=max(ans,C(it->first,it->second));
    }

    cout<<ans<<endl;

    return 0;
}