Harry Potter and the Hide Story

iSea is tired of writing the story of Harry Potter, so, lucky you, solving the following problem is enough.

2

2 2

10 10

Case 1: 1

Case 2: 2

题目大意：

给定 n和k ， 求 n! % k^i 等于0时，i 的最大取值是多少？

解题思路：

将 k分解质因素。n也依据k的质因素求出关系限制i，最后算出最大的i就可以。

解题代码：

#include <iostream>

#include <cstdio>

#include <map>

#include <vector>

#include <cstring>

using namespace std;

typedef unsigned long long ll;

ll n,k;

const int maxn=10000010;

bool isPrime[maxn];

vector <ll> v;

ll tol;

void get_prime(){

    tol=0;

    memset(isPrime,true,sizeof(isPrime));

    for(ll i=2;i<maxn;i++){

        if(isPrime[i]){

            tol++;

            v.push_back(i);

        }

        for(ll j=0;j<tol && i*v[j]<maxn;j++){

            isPrime[i*v[j]]=false;

            if(i%v[j]==0) break;

        }

    }

    //for(ll i=v.size()-1;i>=v.size()-100;i--) cout<<v[i]<<endl;

}

map <ll,ll> getPrime(ll x){

    map <ll,ll> mp;

    for(ll i=0;i<tol && x>=v[i];i++){

        while(x>0 && x%v[i]==0){

            x/=v[i];

            mp[v[i]]++;

        }

    }

    if(x>1) mp[x]++;

    return mp;

}

void solve(){

    if(k==1){

        printf("inf\n");

        return;

    }

    map <ll,ll> mp=getPrime(k);

    ll ans=1e19;

    for(map <ll,ll>::iterator it=mp.begin();it!=mp.end();it++){

        ll tmp=n,sum=0;

        while(tmp>0){

            sum+=tmp/(it->first);

            tmp/=(it->first);

        }

        if(sum/(it->second)<ans) ans=sum/(it->second);

    }

    cout<<ans<<endl;

}

int main(){

    get_prime();

    int t;

    scanf("%d",&t);

    for(int i=0;i<t;i++){

        cin>>n>>k;

        printf("Case %d: ",i+1);

        solve();

    }

    return 0;

}