目录
给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。
两个整数n(2<=n<=1000),a(2<=a<=1000)
一个整数.
输入:
6 10输出:
1
AC代码~
#include<stdio.h>
int num1[1001]; // 存储n!的质因数
int num2[1001]; // 存储a的质因数
int main(){
int a,n,k;
k = 9999;
for(int i=0;i<1001;i++){
num1[i] = 0;
num2[i] = 0;
}
scanf("%d%d",&n,&a);
for(int i=2;i<=n;i++){
int t=i;
int j = 2;
while(t!=1){// 质因数分解
if(t%j == 0){
num1[j]++;
t = t/j;
}
else
j++;
}
}
int j = 2;
while(a!=1){ // 质因数分解
if(a%j == 0){
num2[j]++;
a =a/j;
}
else
j++;
}
for(int i=0;i<1001;i++){
if(num2[i]!=0){
if(num1[i] < k)
k = num1[i];
}
}
printf("%d\n",k);
return 0;
}