ACM 10780 Q10780: Again Prime? No time.
作法 : 模仿 d122. Oh! My Zero!!
當我們要知道N!裡有幾個A的幾次方時,(A是質數)
有一個算法是說 假使答案是A^t
那麼t=(int)N/A+(int)N/(A^2)+(int)N/(A^3)+... (N/A^?=0 停止)
所以我們必須先將M分解得到質因數...然後去看次方
/**********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int Prime[5200]={0},p;
int prime()
{
char num[5001]={0};
int a,b,m=0;
for(a=2;a<5000;a++)
if(num[a]==0)
{
Prime[m]=a;
m++;
for(b=2;a*b<=5000;b++)
num[a*b]=1;
}
return m;
}
int value[50],T[50],top;
int Divisors (int num)
{
int a,b,C=1;
for(a=0;a<p&&Prime[a]*Prime[a]<=num&&num!=1;a++)
{
int time=0;
if(num%Prime[a]==0)
{
while(num%Prime[a]==0)
{
num/=Prime[a];
time++;
}
++top;
value[top]=Prime[a];
T[top]=time;
}
}
if(num!=1)
{
++top;
value[top]=num;
T[top]=1;
}
return C;
}
main()
{
p=prime();
int t,n,m,a,time=0;
/*freopen("input.txt", "rt", stdin);
freopen("output.txt", "w+t", stdout);*/
scanf("%d",&t);
while(t--)
{
scanf("%d %d",&n,&m);
top=0;
Divisors (n);
int MIN=2147483647;
for(a=1;a<=top;a++)
{
int sum=0,temp=value[a];
while(temp<=m)
{
sum+=m/temp;
temp*=value[a];
}
if(sum/T[a]<MIN) MIN=sum/T[a];
}
printf("Case %d:\n",++time);
if(MIN==0) printf("Impossible to divide\n");
else printf("%d\n",MIN);
}
return 0;
}