給定數n，求n!的p進制下有多少個后導零，為了簡化問題，p保證為素數，
如果用大整數寫法，解法可能會超時，
易知，如果一個數可以另外一個數被整除，那么成為這個數的幾倍數的數也可以被整除，
利用這個思路，可以推出“如果可以被p整除，那么這個數的幾倍數的數也可以被整除”，即“如果可以使p進制下形成一個后導0，那么這個數的幾倍數的數也可以如此，而且可能不止一個（與倍數成比例）”
代碼如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int main()
{
int t,n,p,sum=0;
cin>>t;
for(int i=0;i<t;i++){
sum=0;
cin>>n>>p;
for(int k=p;k<=n;k+=p){ //與p成倍數的數肯定會被p整除，所有可以加上p的倍數，列舉n中數，
if(k%p==0){
int te=k;
while(te%p==0){ //如果可以被整除，就除盡，得到倍數，從而得到所有的后導0，
te/=p;
sum++;
}
}
}
cout<<sum<<endl;
}
return 0;
}
代碼如上，歡迎討論，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/231070.html
標籤：其他