学步园

一种是枚举

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define LL long long
int M(int a,int b){
    int r = 1;
    while(b){
        if(b & 1) r *= a;
        a *= a;
        b >>= 1;
    }
    return r;
}
int main(){
    int k;
    scanf("%d",&k);
    while(k--){
        int m,n;
        scanf("%d%d",&n,&m);
        int num = 1,sum = 0;
        while(1){
            LL xx = M(m,num);
            num++;
            if(n < xx) break;
            sum += n / xx;
        }
        printf("%d\n",sum);
    }
    return 0;
}

另一种是在文库上看到的一种计算方法

N! = (m * 1 * m * 2...m *k) * X ( X 与M互质）

N! = k! * m ^ k *X

k * m <= n

k <= n/m

从k!求有多少个m

以此类推

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int main(){
    int k;
    scanf("%d",&k);
    while(k--){
        int n,m;
        scanf("%d%d",&n,&m);
        int s = 0;
        while(n){
            s += n / m;
            n /= m;
        }
        printf("%d\n",s);
    }
    return 0;
}