1871 - 阶乘因式分解（一）

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

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

Input

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

Output

输出m的个数。

Examples

Input

2
100 5
16 2

Output

24
15

Solution C

#include <stdio.h>
int main(){
    int s, i;
    scanf("%d", &s);
    while(s--){
        int t, m, n, cnt = 0;
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++){
            t = i;
            while(t%m == 0){
                cnt++;
                t /= m;
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Solution C++

 #include<iostream>
 using namespace std;
 int main()
 {
     int k,i,j,n,m,w,a;
     cin>>k;
     while(k--)
     {
         w=a=0;
         cin>>n>>m;
         for(i=2;i<=n;i++)
         {
             j=i;
             while(j%m==0&&j)
             {
                 j=j/m;
                 a++;
             }
            w+=a;
             a=0;
         }
         cout<<w<<endl;
     }
     return 0;
 }

Time Limit	3 seconds
Memory Limit	128 MB

Discuss Stats

上一题下一题