[算法]求n!在m进制下末尾有多少个0

参考链接：求n！在m进制下末尾0的个数_.!零n,,m-CSDN博客

我们这里和参考链接不同

使用结构体去存储每个因数的信息

然后使用变量index作为索引，其最终值为因数的个数

具体原理：

例子1：求9！在10进制下的末尾的0的个数

思考1：在10进制下出现0，必须是质数2 与 5组合，所以统计2和5作为因数出现了多少次，取最小的数量就是答案

例子2：求10！在9进制下的末尾的0的个数

思考2：在9进制出现0，其必然是两个3组合起来才会在9进制出现0结尾，所以统计所有因子里面各自出现的次数（这里只有3）然后  整除以 对应因子在进制9里面出现的次数 取最小的那一个值 即是答案！

下面给出一个例题和题解

例题：Contest1035 - NewOJ 2022 Contest 7 - New Online Judge (ecustacm.cn)

题解：

#include<iostream>using namespace std;
#define debug(x) cout<<#x<<" : "<<x<<endl;
typedef long long int ll;const int maxLine=10010; 
struct primeInfo {int nums;int counts;
};
void getPrime(int m);
void printPrimeArray(struct primeInfo arr[maxLine],int len);
int countDivision(int n,int p);struct primeInfo  myPrime[maxLine];
// 记录数量和下标 
int index=0;
int res=0x3f3f3f3f;
int main(){int n,m;
//	cin>>n>>m;n=20;m=14; getPrime(m);
//	printPrimeArray(myPrime,index);for(int i=0;i<index;i++){res=min(res,countDivision(n,myPrime[i].nums)/myPrime[i].counts);}cout<<res;return  0;
} 
// 获取素数个数 
void getPrime(int m){for(int i=2;i*i<=m;i++){// 统计当前因数的个数和具体数值	while(m%i==0){myPrime[index].nums=i;myPrime[index].counts++;m/=i;}if(myPrime[index].counts!=0) index++; }	//如果是合数 那么会在之前统计完//如果是质数 那么本身这个质因数统计不到if (m>1) myPrime[index].nums=m,myPrime[index++].counts++; 
}
// 打印查看 
void printPrimeArray(struct primeInfo arr[maxLine],int len){for(int i=0;i<len;i++){cout<<i<<": "<<arr[i].nums<<" "<<arr[i].counts<<endl;}
}
int countDivision(int n,int p){// 只要不包含1这个参数就一定会结束循环 
//	cout<<"传入参数"<<n<<" "<<p<<endl;int counts=0;
//	debug(counts);while(n>0){counts+=n/p;n/=p;}
//	debug(counts);return counts;
}

中间用到了一点点判断因数范围的小技巧，你发现了吗？