九度oj 题目1104：整除问题

题目描述：: 给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。

输入：: 两个整数n(2<=n<=1000)，a(2<=a<=1000)

输出：: 一个整数.

样例输入：

6 10

样例输出：

1

这道题貌似简单，但对n!，当n = 1000，其值远远超过int的范围，因此不能用简单的方法来求解。
考虑到整除的问题，可以将a拆分成几个质因子的乘积，记录每个质因子的个数，之后对于i从1到n，求解每一个i包含这些质因子的个数并求和。最后算和里总共包括多少个a的质因子个数，即可得出答案
代码如下

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <string>
 5 #include <cmath>
 6 #define MAX 1002
 7 // 15 14 13 12 11 10 8 6 5 4 2 1
 8 // 10   2 5
 9 bool isPrime(int n) {
10     if(n <= 0) {
11         return false;
12     }
13     else if(n == 1) {
14         return false;
15     }
16     else {
17         int two = sqrt(n);
18         for(int i = 2; i <= two; i++) {
19             if(n % i == 0) {
20                 return false;
21             }
22         }
23         return true;
24     }
25 
26 }
27 
28 int yin[MAX];
29 int prime[MAX];
30 int yinCount[MAX];
31 int yinNum[MAX];
32 
33 int main(int argc, char const *argv[])
34 {
35     int n, a;
36     int j = 0;
37     for(int i = 2; i < MAX; i++) {
38         if(isPrime(i) == true) {
39             prime[j] = i;
40             j++;
41         }
42     }
43     int pC = j;
44     while(scanf("%d %d",&n,&a) != EOF) {
45         j = 0;
46         memset(yinCount,0,sizeof(yinCount));
47         memset(yinNum,0,sizeof(yinNum));
48         for(int i = 0; i < pC && prime[i] <= a; i++) {
49             if(a % prime[i] == 0) {
50                 int temp = a;
51                 int tempCount = 0;
52                 while(temp % prime[i] == 0) {
53                     temp = temp/prime[i];
54                     tempCount++;
55                 }
56                 yin[j] = prime[i];
57                 yinNum[j] = tempCount;
58                 j++;
59             }
60         }
61 
62         for(int i = 2; i <= n; i++) {
63             for(int k = 0; k < j; k++) {
64                 if(i % yin[k] == 0) {
65                     int temp = i;
66                     int tempCount = 0;
67                     while(temp % yin[k] == 0) {
68                         temp = temp/yin[k];
69                         tempCount++;
70                     }
71                     yinCount[k] = yinCount[k] + tempCount;
72                 }
73             }
74         }
75 
76        /* for(int i = 0; i < j; i++) {
77             printf("%d %d %d
",yin[i],yinNum[i],yinCount[i]);
78         }*/
79         // 1 2 3 4 5
80         // 2 2 2 2 2
81         int ans = 0;
82         bool flag = true;
83         while(flag) {
84             for(int i  = 0; i <= j; i++) {
85                yinCount[i] = yinCount[i] - yinNum[i];
86                if(yinCount[i] < 0) {
87                     flag = false;
88                     break;
89                }    
90             }
91             if(flag == true) {
92                 ans++;
93             }
94         }
95         
96         printf("%d
",ans);
97     }
98     return 0;
99 }