【Luogu】P3927 SAC E#1 - 一道中档题 Factorial

【题目】洛谷10月月赛R1 提高组

【题意】求n!在k进制下末尾0的个数，n<=1e18,k<=1e16。

【题解】考虑10进制末尾0要考虑2和5，推广到k进制则将k分解质因数。

每个质因数在n!中的数量，以2为例是n/2+n/4+n/8...这样统计。（含x个就被统计x次）

最后得到凑出的k的个数就可以得到末尾0的个数。

分解质因数复杂度O(√k)，也使用pollard rho算法可以加速。

#include <iostream>

#include <stdlib.h>

#include <string.h>

#include <algorithm>

#include <stdio.h>

const int Times = ;

const int N = ;

using namespace std;

typedef long long LL;

LL ct, cnt;

LL fac[N], num[N];

LL gcd(LL a, LL b)

{

    return b? gcd(b, a % b) : a;

}

LL multi(LL a, LL b, LL m)

{

    LL ans = ;

    a %= m;

    while(b)

    {

        if(b & )

        {

            ans = (ans + a) % m;

            b--;

        }

        b >>= ;

        a = (a + a) % m;

    }

    return ans;

}

LL quick_mod(LL a, LL b, LL m)

{

    LL ans = ;

    a %= m;

    while(b)

    {

        if(b & )

        {

            ans = multi(ans, a, m);

            b--;

        }

        b >>= ;

        a = multi(a, a, m);

    }

    return ans;

}

bool Miller_Rabin(LL n)

{

    if(n == ) return true;

    if(n <  || !(n & )) return false;

    LL m = n - ;

    int k = ;

    while((m & ) == )

    {

        k++;

        m >>= ;

    }

    for(int i=; i<Times; i++)

    {

        LL a = rand() % (n - ) + ;

        LL x = quick_mod(a, m, n);

        LL y = ;

        for(int j=; j<k; j++)

        {

            y = multi(x, x, n);

            if(y ==  && x !=  && x != n - ) return false;

            x = y;

        }

        if(y != ) return false;

    }

    return true;

}

LL pollard_rho(LL n, LL c)

{

    LL i = , k = ;

    LL x = rand() % (n - ) + ;

    LL y = x;

    while(true)

    {

        i++;

        x = (multi(x, x, n) + c) % n;

        LL d = gcd((y - x + n) % n, n);

        if( < d && d < n) return d;

        if(y == x) return n;

        if(i == k)

        {

            y = x;

            k <<= ;

        }

    }

}

void find(LL n, int c)

{

    if(n == ) return;

    if(Miller_Rabin(n))

    {

        fac[ct++] = n;

        return ;

    }

    LL p = n;

    LL k = c;

    while(p >= n) p = pollard_rho(p, c--);

    find(p, k);

    find(n / p, k);

}

int main()

{

    LL n,kind;

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

    ct = ;

    find(n, );

    sort(fac, fac + ct);

    num[] = ;

    int k = ;

    for(int i=; i<ct; i++)

    {

        if(fac[i] == fac[i-])

            ++num[k-];

        else

        {

            num[k] = ;

            fac[k++] = fac[i];

        }

    }

    cnt = k;

    LL ans=(1ll<<);

    for(int i=;i<cnt;i++){

        LL as=,N=kind/fac[i];

        while(N){

            as+=N;

            N/=fac[i];

        }

        as/=num[i];

        ans=min(as,ans);

    }

    if(ans==1ll<<)ans=;

    printf("%lld",ans);

    return ;

}