【BZOJ】1951[Sdoi2010]古代猪文

【题意】给定G,N，求：

$$ans=G^{\sum_{i|n}\binom{n}{i}}\ \mod\ \ p$$

1<=N,G<=10^9，p=999911659。

【算法】欧拉定理+组合数取模(lucas)+中国剩余定理(CRT)

【题解】

先考虑简化幂运算，因为模数为素数，由欧拉定理可知G^k=G^(k%φ(p)) mod p，显然G^(k%φ(p)) mod p可以用快速幂求解

但是欧拉定理要求(G,p)=1，当G=p时不满足条件，可以特判答案为0或者用扩展欧拉定理（b%φ(p)+(b>=φ(p)?φ(p):0)）。

故我们实际要求：

$$\sum_{i|n}\binom{n}{i}\ \mod\ \ (p-1)$$

因为p是素数，φ(p)=p-1=999911658=2*3*4679*35617。

因为p-1分解后无平方因子，所以直接用lucas分别对素模数计算后用中国剩余定理合并即可（若有则需要参考bzoj礼物的方法——扩展lucas）

#include<cstdio>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=,MOD=;//999911658=2*3*4679*35617

const int p[]={,,,,};

ll a[],fac[][maxn],n,G;

ll power(ll x,ll k,ll p)

{

    if(x==)return ;

    ll ans=;//快速幂ans=1！

    while(k>)

    {

        if(k&)ans=(ans*x)%p;//满足1时才累乘

        x=(x*x)%p;

        k>>=;

    }

    return ans;

}

ll C(ll n,ll m,ll k)

{

    if(n<m)return ;

    return fac[k][n]*power(fac[k][m],p[k]-,p[k])%p[k]*power(fac[k][n-m],p[k]-,p[k])%p[k];//n!/m!/(n-m)!

}

ll lucas(ll n,ll m,ll k)

{

    if(n<m)return ;

    if(n<p[k]&&m<p[k])return C(n,m,k);

    return C(n%p[k],m%p[k],k)*lucas(n/p[k],m/p[k],k)%p[k];

}

int main()

{

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

    if(G==MOD)

    {

        printf("");

        return ;

    }

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

    {

        fac[k][]=;

        for(int i=;i<p[k];i++)fac[k][i]=fac[k][i-]*i%p[k];//随时记得取模

    }

    for(int i=;i*i<=n;i++)if(n%i==)

    {

        int j=n/i;

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

        {

            a[k]=(a[k]+lucas(n,i,k))%p[k];

            if(i!=j)a[k]=(a[k]+lucas(n,j,k))%p[k];

        }

    }

    ll M=MOD-;

    ll ans=;

    for(int k=;k<=;k++)ans=(ans+a[k]*M/p[k]*power(M/p[k],p[k]-,p[k]))%M;

    printf("%lld",power(G,ans,MOD));

    return ;

}

巴特西

【BZOJ】1951[Sdoi2010]古代猪文

最新文章

热门文章