http://ac.jobdu.com/problem.php?pid=1104
参考了：
1.http://blog.csdn.net/jdplus/article/details/19413037
2.http://blog.csdn.net/jaster_wisdom/article/details/52144308
有两种做法：
第一种做法，把n！做素数分解，用cnt1[i]代表n！中含有的primes[i]的因子个数：如果n/primes[i] == x, 那么在n！中就有x个数含有primes[i]为它的因子，但是这x个数中有的数含有多个primes[i]为它的因子，所以还需要不断的做 cnt1[i] += x/primes[i], x= x/primes[i],直到x == 0。
具体对应代码：
while(t){ cnt1[i] += t/primes[i]; t= t/primes[i]; } 用cnt2[i] 代表a中含有primes[i]的因子个数。
k值为cnt1[i]/cnt2[i]的最大值。
#include <stdio.h> #include <algorithm> using namespace std; int primes[1001]; int primeNum; bool temp[1001]; void init(){ for(int i =0; i<=1000;i++){ temp[i] = true; } for(int i =2; i<=1000;i++){ if(!temp[i]) continue; for(int j = i*i ;j<=1000;j+=i){ temp[j] = false; } } primeNum = 0; for(int i=2;i<=1000;i++){ if(temp[i]){ primes[primeNum++] = i; } } } int main(int argc, char* argv[]) { init(); int cnt1[1001],cnt2[1001]; int a,n; int ans; while(scanf("%d %d" ,&n,&a)!=EOF){ for(int i=0; i<=1000;i++){ cnt1[i] = cnt2[i] = 0; } ans = 0x7fffff; for(int i=0;i<primeNum;i++){ int t = n; while(t){ cnt1[i] += t/primes[i]; t= t/primes[i]; } while(a%primes[i] ==0){ cnt2[i]++; a=a/primes[i]; } if(cnt2[i] == 0) continue; if(cnt1[i]/cnt2[i] < ans){ ans = cnt1[i]/cnt2[i]; } } printf("%d\n",ans); } return 0; }
第二种做法是：
在算n！的时候同时算出k，因为只要factor %a ==0 那么factor=factor/a, k++; 又因为当factor不可以%a==0 时， factor = ma + x。 其中ma是肯定可以被a整除的，i*ma也会被a整除，所以在继续算factor时ma部分不会影响factor%a=0， 所以可以将这部分舍掉，factor = factor%a。
#include <stdio.h> int main(){ int n,a,k; long long factor; while(scanf("%d %d",&n,&a) !=EOF){ factor = 1; k = 0; for (int i = 1; i <=n; ++i) { factor *= i; while(factor%a==0){ k++; factor /= a; } //factor = ma + x, ma will not help to increase k //delete ma to prevent overflow factor = factor % a; } printf("%d\n",k); } }
