【洛谷】SAC E#1 Factorial

别人可以眼杀我却研究了一个小时看了题解才懂的数学题

输入： n, k

输出： n!在k进制下后缀0的个数

n,k <= 10^12

将 n! 表示成 x×2y5z 的形式，其中 x mod 2 != 0,x mod 5 != 0，则答案为 min(y,z)。

所以只需要统计 n! 的质因数分解的结果中，2 和 5 的次数即可。

由于数的乘法对应的是指数的加法，所以求出 [1,n] 中所有数的质因数分解的结果中，2 和 5 的次数，再作和即可。

求一个数 x 中有多少个 p，可以在 O(logx) 时间内完成。

总时间复杂度 O(nlogn)。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll oo = 1e18;

const int N = 100010;

int an;

ll n, k, ans;

ll a[N], b[N], p[N];

template <typename T>

T read(){

    T N(0), F(1);

    char C = getchar();

    for(; !isdigit(C); C = getchar()) if(C == '-') F = -1;

    for(; isdigit(C); C = getchar()) N = N*10 + C-48;

    return N*F;

}

int main(){

    n = read<ll>(); k = read<ll>();

    for(ll i = 2; i*i <= k; i++){

        if(k % i == 0){

            a[++an] = i;

            while(k%i == 0){

                p[an]++;

                k /= i;

            }

        }

    }

    if(k > 1){

        a[++an] = k;

        p[an] = 1;

    }

    ans = oo;

    for(int i = 1; i <= an; i++){

        ll tmp = a[i];

        while(tmp <= n){

            b[i] += n / tmp;

            tmp *= a[i];

        }

        ans = min(ans, b[i]/p[i]);

    }

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

    return 0;

}

巴特西

【洛谷】SAC E#1 Factorial

最新文章

热门文章