链接：http://codeforces.com/problemset/problem/1114/C
题意：给定数字$n$和$b$，问$n!$在$b$进制下有多少后导零。
寒假好像写过这道题当时好像完全不会，之后也没记住写法，今天想做这场的F题看到这道顺便就给切了。
思路：能有后导零就说明$n!$能整除$b$，然后就是求$n!$的阶乘里面$b$的幂次有多少。先分解一下$b$求一下素因子及次数。在对$n!$求一下有素因子的幂次是多少，取比值最小的就是答案。
注意求$n!$里面素因子的幂次时可能会溢出，乘法变成除法即可。
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 1e5 + 10; pair<ll, ll> p[N]; int cnt; ll C(ll x, ll p) { ll res = 0; ll temp = p; while (x >= temp) { res += x / temp; if (x / p < temp) break; temp *= p; } return res; } int main() { ll n, b; scanf("%lld%lld", &n, &b); for (ll i = 2; i * i <= b; i++) { if (b % i == 0) { p[++cnt].first = i; p[cnt].second = 0; while (b % i == 0) { p[cnt].second++; b /= i; } } } if (b != 1) { p[++cnt].first = b; p[cnt].second = 1; } ll ans = 1e18; for (int i = 1; i <= cnt; i++) { ll res = C(n, p[i].first); ans = min(ans, res / p[i].second); } cout << ans << ‘\n‘; return 0; }
Codeforces1114C Trailing Loves (or L'oeufs?)
原文：https://www.cnblogs.com/Mrzdtz220/p/11222759.html
