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
divides 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<m<5000) and n
(0<n<10000). 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 divides n! or a line "Impossible to divide" (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
題意：求N！%M^k==0；最大的k；
思路：先算M的質因子m，並保存質因子的個數，從N開始遞減到N/m，計算每個質因子在N！中出現的次數，取最小。
一開始我的思路是取最大的質因子，然後發現錯了，然後想是質因子*個數最大的那個，然後想了下40，100就不對了。所以就把所有的質因子都算了一次。（本來以為會超時。。。結果142ms過。o(︶︿︶)o 唉）
轉載請注明出處：尋找&星空の孩子
題目連接：http://acm.hust.edu.cn/vjudge/contest/view.action?cid=77956#problem/E
1 #include<stdio.h>
2 #include<string.h>
3 #define LL long long
4 /*
5 bool prime(int x)
6 {
7 for(int i=2;i*i<=x;i++)
8 {
9 if(!(x%i)) return 0;
10 }
11 return 1;
12 }*/
13 LL a[10005];
14 inline void Maxprime(LL x)
15 {
16 LL t=1,k=0;
17 for(LL i=2; i<=x; i++)
18 {
19 while(x%i==0)
20 {
21 t=i;
22 a[i]++;
23 x/=i;
24 }
25 }
26 if(t==1)
27 {
28 a[x]=1;
29 }
30 }
31 inline LL Ssum(LL x)
32 {
33 return (x*(x+1))/2;
34 }
35 LL Sumprime(LL x,LL mod)
36 {
37 LL t=0;
38 while(x)
39 {
40 if(x%mod==0) t++,x/=mod;
41 else return t;
42 }
43 return 0;
44 }
45
46 int main()
47 {
48 LL n,m,T,caseT=1;
49 scanf("%lld",&T);
50 while(caseT<=T)
51 {
52 memset(a,0,sizeof(a));
53 // memset(b,0,sizeof(b));
54 scanf("%lld%lld",&m,&n);
55 LL mod;
56 Maxprime(m);
57 /* if(mod!=m)
58 {
59 LL tt=0;
60 for(LL i=2;i<n;i++)
61 {
62 if(tt<i*a[i])
63 {
64 tt=i*a[i];
65 mod=i;
66 }
67 }
68 }*/
69 // printf("mod=%d\n",mod);
70
71 LL sum,minsum=9999999999;
72 for(LL j=2; j<=m; j++)
73 {
74
75 if(!a[j]) continue;
76 sum=0;
77 for(LL i=n; i>n/j; i--)
78 {
79 LL tmp=Sumprime(i,j);
80 if(tmp) sum+=Ssum(tmp);
81 }
82 if(minsum>sum/a[j]) minsum=sum/a[j];
83 }
84 printf("Case %lld:\n",caseT++);
85 if(!sum) printf("Impossible to divide\n");
86 else printf("%lld\n",minsum);
87 }
88 return 0;
89 }
