CodeForces - 1114C Trailing Loves (or L'oeufs?) (质因子,阶乘分解)
程序员文章站
2022-07-12 13:42:07
...
void solve()
{
ll n, b;cin >> n >> b;
//处理出b的所有素因子并记录下次数x,检查该素因子在n!中的幂次y
//对所有素因子取一个最小值
vector<pair<ll,ll> > prime;
for (ll i = 2; i * i <= b; ++i)
{
ll num = 0;
while (b % i == 0) ++num,b /= i;
if (num) prime.push_back(make_pair(i, num));
}
if(b>1) prime.push_back(make_pair(b,1));
ll ans = 1ll<<60;
for (auto x : prime)
{
ll nn = n, sum = 0;
while (nn)
{
sum += (nn / x.first);
nn /= x.first;
}
ans = min(ans, sum / x.second);
}
cout << ans << endl;
}
signed main()
{
int T = 1;
while (T--) solve();
return 0;
}