HDU 3988 大数分解

题意：

这题把k素因子分解后看n!中有多少个与k对应的素因子。

n!中含有素因子p的个数为n/p+n/p^2.....取整。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const unsigned long long oo=9223372036854775808ULL;
ll gcd(ll a,ll b)
{
    return (b==0)?a:gcd(b,a%b);
}
ll Mulmod(ll a,ll b,ll n)
{
    ll  exp = a%n, res = 0;
    while(b)
    {
        if(b&1)
        {
            res += exp;
            if(res>n) res -= n;
        }
        exp <<= 1;
        if(exp>n)
            exp -= n;
        b>>=1;
    }
    return res;
}
ll exp_mod(ll a,ll b,ll c)
{
    ll k = 1;
    while(b)
    {
        if(b&1)
            k = Mulmod(k,a,c);
        a = Mulmod(a,a,c);
        b>>=1;
    }
    return k;
}
bool Miller_Rabbin(ll n, ll times)
{
    if(n==2)return 1;
    if(n<2||!(n&1))return 0;

    ll a, u=n-1, x, y;
    int t=0;
    while(u%2==0)
    {
        t++;
        u/=2;
    }
    srand(100);
    for(int i=0; i<times; i++)
    {
        a = rand() % (n-1) + 1;
        x = exp_mod(a, u, n);
        for(int j=0; j<t; j++)
        {
            y = Mulmod(x, x, n);
            if ( y == 1 && x != 1 && x != n-1 )
                return false; //must not
            x = y;
        }
        if( y!=1) return false;
    }
    return true;
}
ll Pollard_Rho(ll n,ll c)
{
    ll x,y,d,i=1,k=2;
    y = x = rand() % (n-1) + 1;
    while(1)
    {
        i++;
        x = (Mulmod(x,x,n) + c)%n;
        d = gcd((x-y+n)%n,n);
        if(d>1&&d<n)
            return d;
        if(x==y)
            return n;
        if(i==k)
        {
            k<<=1;
            y = x;
        }
    }
}
ll factor[550],tol;
void Find_factor(ll n,ll c)
{
    if(n==1)
        return;
    if(Miller_Rabbin(n,10))
    {
        factor[tol++] = n;
        return;
    }
    ll p = n;
    ll k = c;
    while(p>=n)
        p = Pollard_Rho(p,c--);
    Find_factor(p,k);
    Find_factor(n/p,k);
}
int main()
{
    int t,ca=0,num;
    unsigned long long n,k,fac[550][2];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%I64u%I64u",&n,&k);
        printf("Case %d: ",++ca);
        if(k==1)
        {
            puts("inf");
            continue;
        }
        tol=0;
        Find_factor(k,120);
        unsigned long long ans=oo;
        sort(factor,factor+tol);
        num=0;
        memset(fac,0,sizeof(fac));
        fac[0][0]=factor[0],fac[0][1]=1;
        for(int i=1; i<tol; i++)
        {
            if(fac[num][0]!=factor[i])
                num++,fac[num][0]=factor[i];
            fac[num][1]++;
        }
        for(int i=0; i<=num; i++)
        {
            unsigned long long wans=0,wdiv=fac[i][0],d=n;
            while(d)
                wans+=d/wdiv,d/=wdiv;
            ans=min(ans,wans/fac[i][1]);
        }
        if(ans==oo)
            puts("inf");
        else
            printf("%I64u\n",ans);
    }
    return 0;
}