数论全家桶？

题意描述

完整版

简单版：

给定 $g,n(g,n\le10^9)$，求 $g^{\sum_{d\mid n}{C_{n}^{d}}} \mod{999911659} $。

做法

首先根据欧拉定理推出：

$$ g^{\sum_{d\mid n}{C_{n}^{d}}} \equiv g^{\sum_{d\mid n}{C_{n}^{d}}\mod{999911658}} (\bmod{999911659}) $$

所以我们只需要求出 $\sum_{d\mid n}{C_{n}^{d}}\mod{999911658}$ 即可，容易想到用卢卡斯定理。

但是 $999911658$ 显然不是个质数，所以我们将其质因数分解。

$$ 999911659=35617\times4679\times3\times2 $$

于是我们只需要用分解后的质数分别对 $\sum_{d\mid n}{C_{n}^{d}}$ 进行计算，然后再套一遍中国剩余定理即可（当然，你可以也枚举 $\lfloor\frac{ans}{35617}\rfloor$ 的值）。

最后再算一次快速幂即可得到答案。

时间复杂度 $O(\sqrt{n}\log{n}\log{999911659})$。

code

#include<cmath>
#include<iostream>
#define int long long
using namespace std;
int P[5]={999911659,35617,4679,3,2};
int s[1000005],p=1,d[1000005];
int a[15],mod[15],m[15],n,ans,g;
void exgcd(int a,int b,int &x,int &y)
{
    if(b==0){x=1;y=0;return;}
    exgcd(b,a%b,x,y);
    int z=x;x=y,y=z-y*(a/b);
}
int qpow(int x,int y,int P)
{
    int ans=1;
    for(;y;y>>=1)
    {
        if(y&1)ans=ans*x%P;
        x=x*x%P;
    }
    return ans;
}
int C(int x,int y,int P){return x>y?0:s[y]*d[y-x]%P*d[x]%P;}
int Lucas(int x,int y,int P)
{
    if(y==0)return 1;
    return Lucas(x/P,y/P,P)*C(x%P,y%P,P)%P;
}
void work(int k)
{
    int mod=P[k];
    s[0]=d[0]=1;
    for(int i=1;i<mod;i++)
    {
        s[i]=(s[i-1]*i)%mod;
        d[i]=qpow(s[i],mod-2,mod);
    }
    for(int i=1;i<=sqrt((long long)n);i++)
    {
        if(!(n%i))
        {
            a[k]=(a[k]+Lucas(i,n,mod))%mod;
            if(i*i==n)continue;
            a[k]=(a[k]+Lucas(n/i,n,mod))%mod;
        }
    }
    m[k]=mod;
    p*=mod;
}
signed main()
{
    scanf("%lld%lld",&n,&g);
    if(!(g%P[0]))return!printf("0");
    for(int i=1;i<=4;i++)work(i);
    for(int i=1;i<=4;i++)
    {
        mod[i]=p/m[i];
        int x=0,y=0;
        exgcd(mod[i],m[i],x,y);
        ans+=a[i]*mod[i]*(x<0?x+m[i]:x);
        ans%=p;
    }
    printf("%lld",qpow(g,ans,P[0]));
}