题目 https://codeforces.com/contest/1114/problem/C
思路
求 n！ 转化为 b 进制下末尾有多少个 0.
解题思路：
原题：swjtuOJ 2090
这是一道很好的数论题。
首先转换一下思路：
要求 n! 在 b 进制下有多少个尾 0 就相当于 求 n! % (b^k) == 0 的最大 k。
那么我们现在把 n! 看作一个数 A。问题就是 求 A % (b^k) == 0 的最大 k;
我们知道有素数分解定理： b = p1^a1 * p2^a2 * p3^a3 ...；
那么我们如果可以求得 A 里面 p1^b1 * p2^b2 * p3^b3 ... 的 b1, b2, b3...
那么答案 ans = min(ans, ai/bi ) 了也就是要整除，首先要满足最小的那个能整除。
(1)首先对 b 进行素因子分解，直接暴力（log b）, 用一个数组离散化形成该素因子的编号和该素因子的幂的映射 或者 用map存储该素因子的幂，得到所有素因子以及素因子的幂
(2)对于每一个素因子p，计算对应的 A（即 n! ) 中素因子p的幂，两者相除取所有p幂的最小值就是对应的最大整数。
这里求 n! 下 素因子 p 的幂 用累除法，因为存在推论：
n！ 下 p 的幂 = [ n/p ] + [ n/(p^2) ] + [ n/(p^3) ] ...
代码
#include <bits/stdc++.h>using namespace std;
typedef long long ll;const int MAXN = 2e6+1000;
ll N, B;
vector<ll>prime;
map<ll, int>mmp;
void get_p(ll n)
{ll len = sqrt((double)n);for(ll i = 2; i <= len; i++){if(n%i == 0){prime.push_back(i);while(n%i == 0){n/=i;mmp[i]++;}}}if(n != 1){prime.push_back(n);mmp[n]++;}
}ll calc(ll n, ll p)
{ll res = 0;while(n){res += n/p;n/=p;}return res;
}int main()
{ll sum = 1ll;scanf("%lld %lld", &N, &B);get_p(B);ll ans = (1ll<<62);for(ll i = 0; i < prime.size(); i++){ans = min(ans, calc(N, prime[i])/mmp[prime[i]]);}printf("%I64d\n", ans);return 0;
}