HDU 3988(数论)

浅浅的花香味﹌ 2022-05-31 05:06 134阅读 0赞

问题描述:

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

![3b2eeb33c7d601e6b67343855809d70b_v_1517737046][] Input

The first line contains a single integer T, indicating the number of test cases.   
Each test case contains two integers, N and K.   
  
Technical Specification   
  
1. 1 <= T <= 500   
2. 1 <= K <= 1 000 000 000 000 00   
3. 1 <= N <= 1 000 000 000 000 000 000

Output

For each test case, output the case number first, then the answer, if the answer is bigger than 9 223 372 036 854 775 807, output “inf” (without quote).

Sample Input

2
    2 2
    10 10

Sample Output

Case 1: 1
    Case 2: 2

题目分析:我们对k进行质因子分解，保存种类和对应的指数（factor\[i\]\[0\]种类,factor\[i\]\[1\]个数)，我们也相应的求出N!中factor\[i\]\[0\]的个数a,则ans=min(ans,a/factor\[i\]\[1\]);

当k为1时则为inf

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll  long long
    using namespace std;
    
    const int maxn=1e7+100;
    int prime[maxn],cnt;
    bool vis[maxn];
    
    void get_prime()//素数打表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    ll factor[1000][2],fcnt;
    void get_factor(ll m)//求质因子
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&(ll) (prime[i]*prime[i])<=m;i++) {
            if (m%prime[i]==0) {
                factor[fcnt][0]=prime[i];
                while (m%prime[i]==0) {
                    factor[fcnt][1]++;
                    m=m/prime[i];
                }
                fcnt++;
            }
        }
        if (m!=1) {
            factor[fcnt][0]=m;
            factor[fcnt][1]=1;
            fcnt++;
        }
    }
    ll solve(ll m,ll k)//求m!中因子k的个数
    {
        if (m/k==0) return 0;
        else return m/k+solve(m/k,k);
    }
    int main()
    {
        int t,icase=1;
        get_prime();
        scanf("%d",&t);
        while (t--) {
            ll n,k;
            scanf("%lld%lld",&n,&k);
            if (k==1) {
                printf("Case %d: inf\n",icase++);
                continue;
            }
            get_factor(k);
            ll ans=1e18;
            for (int i=0;i<fcnt;i++) {
                ans=min(ans,solve(n,factor[i][0])/factor[i][1]);
            }
            printf("Case %d: %lld\n",icase++,ans);
        }
        return 0;
    }

[3b2eeb33c7d601e6b67343855809d70b_v_1517737046]: https://odzkskevi.qnssl.com/3b2eeb33c7d601e6b67343855809d70b?v=1517737046