阶乘因式分解（二）【南阳oj 题目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.

    给大家举一个简单的列子：

     求10!中可以分解出几个2

10!=1*（2）*3*（4）*5*（6）*7*（8）*9*（10  ）          【里面一共有10/2=5个数可以分解出2，即2,4,6,8,10】

   =1*（2*1）*3*（2*2）*5*（2*3）*7（2*4）*9*（2*5）     【里面还有10/2/2=5/2=2（取整）个数还可以继续分出2，即2,4】

   =1*（2*1）*3*（2*(2*1））*5*（2*3）*7*（2*（2*2）*9*（2*5）【里面还有10/2/2/2=5/2/2=1（取整）个数还可以继续分出2，即2】

   =1*（2*1）*3*（2*(2*1））*5*（2*3）*7*（2*（2*（2*1））*9*（2*5）【里面没有可以再分出2的数了，所以一共可以分出10/2+10/2/2+10/2/2/2=5+2+1=8（取整）个2】

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{int t;long long n,m,s;cin>>t;while(t--){	s=0;cin>>n>>m;for(int i=0;;i++){   s=s+n/m;if(n/m>=m)n=n/m;else{cout<<s<<endl;break;}	}}return 0;
}