HDU/HDOJ 3988 2011 WHU多校联合 Harry Potter and the Hide Story

Harry Potter and the Hide Story

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1Accepted Submission(s): 1

Problem Description

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

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).

SampleInput

2
2 2
10 10

SampleOutput

Case 1: 1
Case 2: 2

Author

iSea@WHU

解题方法当然是把k质因数分解之后，分别判断每一个素因子在阶乘里面出现了多少次，然后取所有素因子出现次数的最小值即可

由于数据量比较大，我用的米勒罗宾素数测试进行的素因子分解。

我的代码：

#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>

using namespace std;

typedef unsigned __int64 ll;
#define INF (__int64)9223372036854775807
const int MAX=100;

ll myrandom()
{
	ll a;
	a=rand();
	a=a*rand();
	a=a*rand();
	a=a*rand();
	return a;
}

ll mulmod(ll a,ll b,ll c)
{
	ll ret=0;
	while(b)
	{
		if(b&1)
		{
			ret=ret+a;
			if(ret>c)
				ret=ret-c;
		}
		a<<=1;
		if(a>c)
			a-=c;
		b>>=1;
	}
	return ret;
}

ll powmod(ll a,ll b,ll c)
{
	ll ret=1;
	while(b)
	{
		if(b&1)
			ret=mulmod(ret,a,c);
		a=mulmod(a,a,c);
		b>>=1;
	}
	return ret;
}

bool miller(ll base,ll n)
{
	ll m=n-1,k=0,i;
	while(m%2==0)
	{
		m>>=1;
		k++;
	}
	if(powmod(base,m,n)==1)
		return true;
	for(i=0;i<k;i++)
	{
		if(powmod(base,m<<i,n)==n-1)
			return true;
	}
	return false;
}

bool miller_rabin(ll n)
{
	int i;
	for(i=2;i<100;i++)
		if(n%i==0)
			if(n==i)
				return true;
			else
				return false;
	for(i=0;i<MAX;i++)
	{
		ll base=myrandom()%(n-1)+1;
		if(!miller(base,n))
			return false;
	}
	return true;
}

ll gcd(ll a,ll b)
{
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}

ll f(ll a,ll b)
{
	return (mulmod(a,a,b)+1)%b;
}

ll pollard_rho(ll n)
{
	int i;
	if(n<=2)
		return 0;
	for(i=2;i<100;i++)
		if(n%i==0)
			return i;
	ll p,x,xx;
	for(i=1;i<MAX;i++)
	{
		x=myrandom()%n;
		xx=f(x,n);
		p=gcd((xx+n-x)%n,n)%n;
		while(p==1)
		{
			x=f(x,n);
			xx=f(f(xx,n),n);
			p=gcd((xx+n-x)%n,n)%n;
		}
		if(p)
			return p;
	}
	return 0;
}

ll prime(ll a)
{
	if(miller_rabin(a))
		return 0;
	ll t=pollard_rho(a);
	ll p=prime(t);
	if(p)
		return p;
	return t;
}

ll max(ll a,ll b)
{
	if(a>b)
		return a;
	else
		return b;
}

ll getans(ll m,ll n)
{
	ll ans=0,t=n;
	while(t)
	{
		t=t/m;
		ans=ans+t;
	}
	return ans;
}

int main()
{
	int t,T;
	ll n,k,maxfac,tmp,ans,bingshen,acm;
	scanf("%d",&T);
	for(t=1;t<=T;t++)
	{
		scanf("%I64d%I64d",&n,&k);
		if(k==1)
		{
			printf("Case %d: inf\n",t);
			continue;
		}
		maxfac=0,ans=INF;
		while(k>1)
		{
			bingshen=0;
			if(miller_rabin(k))
			{
				acm=getans(k,n);
				if(acm<ans)
					ans=acm;
				break;
			}
			tmp=prime(k);
			k=k/tmp;
			bingshen++;
			while(k%tmp==0)
			{
				k=k/tmp;
				bingshen++;
			}
			acm=getans(tmp,n);
			acm=acm/bingshen;
			if(acm<ans)
				ans=acm;
		}
		if(ans>=INF)
			printf("Case %d: inf\n",t);
		else
			printf("Case %d: %I64d\n",t,ans);
	}
	return 0;
}