阶乘因式分解（二）

时间限制：

3000 ms  |  内存限制：

65535 KB

难度：

3

 

描述

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

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

注：^为求幂符号。

 

 

 

输入

第一行是一个整数s（0<s<=100)，表示测试数据的组数

随后的s行, 每行有两个整数n，m。

输出

输出m的个数

样例输入

3100 516 21000000000  13

样例输出

241583333329 代码一：

1 #include
         
            2 using namespace std;  3 int main()  4 {  5     int t;  6     cin>>t;  7     while(t--)  8     {  9         int n,m; 10         cin>>n>>m; 11         int cnt=0; 12         if(n%m) 13             n-=n%m; 14         for(int i=n;i>=2;) 15         { 16             int x=i; 17             while(x%m==0) 18             { 19                 cnt++; 20                 x=x/m; 21             } 22             i-=m; 23         } 24         cout<
          
           <
          
         

 代码二：

1 #include 
         
           2 #include 
          
            3  4 using namespace std; 5  6 int main() 7 { 8     int T, n, m, cnt; 9     scanf("%d", &T);10     while(T--)11     {12         scanf("%d%d", &n, &m);13         cnt = 0;14         while(n)15         {16             cnt += n/m;//每次找出含有 m ,m^2......的项的个数17             n = n/m;18         }19         printf("%d\n", cnt);20     }21     return 0;22 }