n! 在m进制下末尾0的个数（含大量注释）
一、思路：
1、先从10进制思考
可以先从10进制下末尾0的个数开始思考，先求出10的质因数，很显然是2 * 5，因此我们需要求n！的结果有多少2 * 5，但是我们先求n！有多少2以及有多少5，之后取最小的那个值即为有多少个2 *5了。举个例子，要求320有多少2 * 5，320 = 262^626 * 5，那么显然只有一个2 * 5，所以320在10进制下末尾就只有一个0。之后加入阶乘思考，例如思考25！在十进制下末尾有多少0，这里我们引入一个公式：
那么可以计算出25！有22个2，6个5，那么25！的末尾就有6个0了。
2、推广到m进制
通过对10进制的思考，可以类比到任意的m进制，例如求n！在3进制下末尾0的个数，即找n！里有几个3。再例如求n！在9进制下末尾0的个数，由于33=9，即找n！里有几个33，即3的个数除以2。
二、代码
#include<iostream> #include<algorithm> #include<vector> #include<string> using namespace std; #define ll long long const ll maxn = 1e6 + 5; const ll mod = 1e9 + 7; const double eps = 1e-9; const double pi = acos(-1.0); const ll inf = 0x3f3f3f3f; ll n, b;//n是底数，b是进制，例如5的二进制，那么n是5，b是2 ll prime[maxn];//记录每个元素是不是质数，prime[i] = 0说明i是质数 vector<ll> ve;//记录所有的质数 /* 初始化 首先对prime初始化，如果prime中元素对应的下标i是质数，那么prime[i]是0 将质数都加入到ve中 */ void init() { for (ll i = 2; i <= 1000000; i++) { if (!prime[i]) { ve.push_back(i); for (ll j = 2 * i; j <= 1000000; j += i) { prime[j] = 1; } } } } //依据博客里的公式求x!里有有少个质因数pp ll get(ll pp, ll x) {//pp是进制b的一个质因数，x是底数n ll res = 0; while (x) { res += x / pp; x /= pp; } return res; } ll cnt[maxn], num[maxn]; void solve() { ll f = b; //计算进制b的质因数，cnt记录数量，例如b = 18，18 = 2*3*3， 那么cnt[2]=1，cnt[3]=2 for (ll i = 0; i < ve.size(); i++) { if (f == 1) break; while (f%ve[i] == 0) { cnt[ve[i]]++; f /= ve[i]; } } //这一步是求对于底数n的每一个质因数ve[i]，求出n！有多少个ve[i] for (ll i = 0; i < ve.size(); i++) { if (cnt[ve[i]]) { num[ve[i]] = get(ve[i], n); } } ll ans = 1e18 + 10; if (f != 1) ans = min(ans, get(f, n)); /* 这一步除法是求出n！的每一个因数的个数 例如当进制是18时，18 = 2*3*3 那么求出来质因数3的个数后，显然需要除以2，因为我们最终是希望得到2*9（18）的个数 */ for (ll i = 0; i < ve.size(); i++) { if (cnt[ve[i]]) { ans = min(ans, num[ve[i]] / cnt[ve[i]]); } } cout << ans << endl; }
作者：lizefeng1998
链接：https://juejin.cn/post/7023703649452818440