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

HDU 3988 Harry Potter and the Hide Story（数论-整数和素数）,布布扣,bubuko.com

HDU 3988 Harry Potter and the Hide Story（数论-整数和素数）

原文：http://blog.csdn.net/a1061747415/article/details/38316009