JOI 2007 春合宿 Factorial ( Binary Search )

http://www.ioi-jp.org/camp/2007/2007-sp-tasks/2007-sp-day1_20.pdf
factorial: 階乗 (Factorial) - 2007年 日本情報オリンピック春合宿OJ | AtCoder
First we will decompose N into powers of prime factors. Anything left after decomposing the first sqrt( N ) prime factors will first be the minimum, and its job is done. Then we should look for each powers of prime factor p ^ n individually and take the maximum, for minimum number x that satisfies p ^ n | x!. I did this with binary search on n.

bool ok( int x, int p, int n ){ // is p ^ n divisible by x!
    int cnt = 0;
    while( x )
        cnt += x / p,
        x /= p;
    return cnt >= n;
}

int solve1( int p, int n ){ // min factorial divisible by p ^ n
    int res = -1;
    int lb = 1, rb = 1e8;
    while( lb <= rb ){
        int mid = lb + rb >> 1;
        if( ok( mid, p, n ) ) res = mid, rb = mid - 1;
        else lb = mid + 1;
    }
    return res;
}

void solve(){
    int N; cin >> N;

    vector< pair< int, int > > factor; // p ^ n
    int sqrN = sqrt( N );
    for( int i = 2; i <= sqrN; ++i ){
        if( N % i == 0 ){
            factor.push_back( { i, 0 } );
            while( N % i == 0 )
                ++factor[ factor.size() - 1 ].second,
                N /= i;
        }
    }

    int ans = N;
    for( int i = 0; i < factor.size(); ++i ){
        int p = factor[ i ].first;
        int n = factor[ i ].second;
        ans = max( ans, solve1( p, n ) );
    }

    cout << ans << "\n";
}