Again Prime? No Time.（uva10870+数论）
2015-05-15 10:40:49         来源：寻找&星空の孩子

Again Prime? No time.
Input: standard input
Output: standard output
Time Limit: 1 second

The problem statement is very easy. Given a number n you have to determine the largest power of m, not necessarily prime, that pides n!.

Input

The input file consists of several test cases. The first line in the file is the number of cases to handle. The following lines are the cases each of which contains two integers m (1 and n (0. The integers are separated by an space. There will be no invalid cases given and there are not more that500 test cases.

Output

For each case in the input, print the case number and result in separate lines. The result is either an integer if m pides n! or a line "Impossible to pide" (without the quotes). Check the sample input and output format.

Sample Input

2
2 10
2 100

Sample Output

Case 1:
8
Case 2:
97

```#include
#include
#define LL long long
LL a[10005];
inline void Maxprime(LL x)
{
LL t=1,k=0;
for(LL i=2; i<=x; i++)
{
while(x%i==0)
{
t=i;
a[i]++;
x/=i;
}
}
if(t==1)
{
a[x]=1;
}
}
inline LL Ssum(LL x)
{
return (x*(x+1))/2;
}
LL Sumprime(LL x,LL mod)
{
LL t=0;
while(x)
{
if(x%mod==0) t++,x/=mod;
else return t;
}
return 0;
}

int main()
{
LL n,m,T,caseT=1;
scanf("%lld",&T);
while(caseT<=T)
{
memset(a,0,sizeof(a));
scanf("%lld%lld",&m,&n);
LL mod;
Maxprime(m);

LL  sum,minsum=9999999999;
for(LL j=2; j<=m; j++)
{

if(!a[j]) continue;
sum=0;
for(LL i=n; i>n/j; i--)
{
LL tmp=Sumprime(i,j);
if(tmp) sum+=Ssum(tmp);
}
if(minsum>sum/a[j]) minsum=sum/a[j];
}
printf("Case %lld:\n",caseT++);
if(!sum) printf("Impossible to pide\n");
else printf("%lld\n",minsum);
}
return 0;
}
```