NYOJ 70

描述：给定两个数n，m,其中m是一个素数。

将n（0<=n<=2^31）的阶乘分解质因数，求其中有多少个m。

注：^为求幂符号。

输入：

　　第一行是一个整数s（0<s<=100)，表示测试数据的组数
　　随后的s行, 每行有两个整数n，m。 

输出：

　　输出m的个数

样例输入

　　3

　　100 5

　　16 2

　　1000000000 13

样例输出

　　

24 　　15 　　83333329

　　当n,m体量很小的时候，用这个代码就可以AC：

 #include <iostream>
using namespace std;

//测试分解test中有多少个m 
int num_m(int test,int m){
    int res = 0;
    while(test%m==0){
        res++;
        test/=m;
    }
    return res;
}

int main(){
    int s; 
    cin>>s;
    while(s--){
        int n,m ;
        cin>>n>>m ;
        int res = 0;
        for(int i=n;i>=1;i-- ){
            res+= num_m(i,m);                    
        }
        cout<<res<<endl;
    }
    
}         

但是实际情况是这个数还是比较大的，已经达到了2^31量级，所以上面暴力的解法是超时的。

接下来我们考虑：比如n=100,m=5.的情况，这个时候100当中有5，10，15，20，25，30，35，40，45，50，55，60，65，70，75，80，85，90，95，100

这些数能够整除5；其中25,50,75,100又能整除25=5^2,所以可以分解出两个5，因为第一遍的时候已经加过一次了，所以最多只能分解出20+4=24个5.

按照这个思想，我们不妨设置这样一个算法：让n循环除以m，每次得到的商是本次循环中能够整除m的个数，然后n=n/m赋予n新值。n缩小为原来的1/m,继续循环直到n=0为止。这样以来，"数值上接近于n的那些数能够分解质因数m的个数"恰好等于"接近于m及m的小倍数的这些数的计算的次数"，如此对称下去,从而巧妙的完成了计算。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>

int main(){
    int N;
    scanf("%d",&N);
    while(N--){
        int n,m,sum=0;
        scanf("%d%d",&n,&m);
        while(n){
            sum+=n/m;//计算n中有多少个能整除m的数;  
            n/=m;     // 计算n中有多少个能够整除m^2的数；
            
            //n = n/m  这样就把n的大小缩小成了原来的（1/m）  
        } 
        printf("%d
",sum);
    }
    
    return 0;
}