给定数n，求n!的p进制下有多少个后导零

 

题目描述

这是一道很简单的中学数学题：

给定数n，求n!的p进制下有多少个后导零。非常简单。

为了简化问题，p保证为素数。

输入描述:

第一行给定一个数t，表示有t组输入

接下来t行，每行给定两个数n,p；意义如题所示；

输入范围：(t<=1000) (1<=n<=1000000 ） (2<=p<=1000000)

输出描述:

对于每一组输入，输出单独的一行表示答案。

示例1

输入

复制2 2 2 3 2

2
2 2
3 2

输出

复制1 1

1
1

#include <bits/stdc++.h>
using namespace std;
#define PB push_back
#define LL long long
#define PII pair<int,int>
#define FI first
#define SE second
#define endl '\n'
const double pi=acos(-1.0);
const int N=1e6+10,M=1e6+10,mod=1e9+7,INF=0x3f3f3f3f;
int n,p;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int s[2020][2020];
void solve(){
    cin>>n>>p;
    int ans=0;
    while(n>=p){
        ans+=n/p;
        n/=p;
    }
    cout<<ans<<'\n';
}
int main()
{
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/*
*/