欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

CodeForces - 1114C Trailing Loves (or L'oeufs?) (质因子,阶乘分解)

程序员文章站 2022-07-12 13:42:07
...

???? ???? ????
关于阶乘分解
CodeForces - 1114C Trailing Loves (or L'oeufs?) (质因子,阶乘分解)

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;
}