- 题目描述：
给定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的质因子个数，即可得出答案
代码如下#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 1002
// 15 14 13 12 11 10 8 6 5 4 2 1
// 10 2 5
bool isPrime(int n) {
if(n <= ) {
return false;
}
else if(n == ) {
return false;
}
else {
int two = sqrt(n);
for(int i = ; i <= two; i++) {
if(n % i == ) {
return false;
}
}
return true;
} } int yin[MAX];
int prime[MAX];
int yinCount[MAX];
int yinNum[MAX]; int main(int argc, char const *argv[])
{
int n, a;
int j = ;
for(int i = ; i < MAX; i++) {
if(isPrime(i) == true) {
prime[j] = i;
j++;
}
}
int pC = j;
while(scanf("%d %d",&n,&a) != EOF) {
j = ;
memset(yinCount,,sizeof(yinCount));
memset(yinNum,,sizeof(yinNum));
for(int i = ; i < pC && prime[i] <= a; i++) {
if(a % prime[i] == ) {
int temp = a;
int tempCount = ;
while(temp % prime[i] == ) {
temp = temp/prime[i];
tempCount++;
}
yin[j] = prime[i];
yinNum[j] = tempCount;
j++;
}
} for(int i = ; i <= n; i++) {
for(int k = ; k < j; k++) {
if(i % yin[k] == ) {
int temp = i;
int tempCount = ;
while(temp % yin[k] == ) {
temp = temp/yin[k];
tempCount++;
}
yinCount[k] = yinCount[k] + tempCount;
}
}
} /* for(int i = 0; i < j; i++) {
printf("%d %d %d\n",yin[i],yinNum[i],yinCount[i]);
}*/
// 1 2 3 4 5
// 2 2 2 2 2
int ans = ;
bool flag = true;
while(flag) {
for(int i = ; i <= j; i++) {
yinCount[i] = yinCount[i] - yinNum[i];
if(yinCount[i] < ) {
flag = false;
break;
}
}
if(flag == true) {
ans++;
}
} printf("%d\n",ans);
}
return ;
}