HDU 3988(数论)-蒲公英云

HDU 3988(数论)

问题描述:

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 <= T <= 500
1 <= K <= 1 000 000 000 000 00
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;
}