CF-1114C-Trailing Loves (or L'oeufs?)

题意：

输入n和m，求n!转换成m进制之后末尾有多少个0；

思路：

转换一下题意就可以看成，将n表示成x * (m ^ y)，求y的最大值。^表示次方而不是异或；

这就比较好想了，将m分解质因数，对于每个质因数，设n!含有a个，m含有b个，则ans = min(ans, a / b);

自己比赛的时候写的

C - Trailing Loves (or L'oeufs?)

GNU C++11

Accepted

46 ms

0 KB

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

map<LL, LL> mp, num;

vector<LL> vc;

int main() {

    LL n, m;

    scanf("%lld%lld", &n, &m);

    for (LL i = ; i * i <= m; i++) {

        if (m % i == ) {

            vc.push_back(i);

            while (m % i == ) {

                m /= i;

                mp[i]++;

            }

        }

    }

    if (m != ) {

        vc.push_back(m);

        mp[m]++;

    }

    for (int i = ; i < vc.size(); i++) {

        LL j = ;

        while (j <= n / vc[i]) {

            j *= vc[i];

            num[vc[i]] += n / j;

        }

    }

    LL ans = 1LL << ;

    for (LL i = ; i < vc.size(); i++) {

        ans = min(ans, num[vc[i]] / mp[vc[i]]);

    }

    printf("%lld\n", ans);

    return ;

}

其实没必要把各个因子保存下来。标程还是优很多的

看了标程之后改的

C - Trailing Loves (or L'oeufs?)

GNU C++11

Accepted

31 ms

0 KB

#include "bits/stdc++.h"

using namespace std;

typedef long long LL;

const LL INF = 1LL << ;

int main() {

    LL n, m, ans = INF;

    scanf("%lld%lld", &n, &m);

    for (LL i = ; i <= m; i++) {

        if (i * i > m) {

            i = m;

        }

        if (m % i == ) {

            int cnt = ;

            while (m % i == ) {

                m /= i;

                cnt++;

            }

            LL tmp = , mul = ;

            /*

             for (LL mul = i; mul <= n; mul *= i)

             这种写法应该更符合正常思维，但是因为n最高可以达到1e18，比较接近LL上限，mul可能乘i之前还小于n,乘完就爆LL了；

            */

            while (mul <= n / i) {

                mul *= i;

                tmp += n / mul;

            }

            ans = min(ans, tmp / cnt);

        }

    }

    printf("%lld\n", ans);

    return ;

}

巴特西

CF-1114C-Trailing Loves (or L'oeufs?)

最新文章

热门文章