bzoj 1951: [Sdoi2010]古代豬文

題意：

求這個東西：

G∑k|nkCknmod 999911659

題解：

這題就是把幾個模闆弄在一起。

首先歐拉定理：

G∑k|nkCknmod ϕ(999911659)mod 999911659

=G∑k|nkCknmod 999911658mod 999911659

然後将999911658拆成2*3*4679*35617四個質數，然後lucas求組合數，再中國剩餘定理合并就可以了。

這種SB題調了一小時真的菜

code：

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#define LL long long
using namespace std;
LL p[]={,,,};
const LL mod=,MOD=;
LL n,g,f[][],inv[][],b=;
LL pow(LL a,LL b,LL mod)
{
    LL ans=;
    while(b)
    {
        if(b&) ans=ans*a%mod;
        a=a*a%mod;b>>=;
    }
    return ans;
}
LL C(LL n,LL m,LL op)
{
    if(m>n) return ;
    return f[op][n]*inv[op][n-m]%p[op]*inv[op][m]%p[op];
}
void pre()
{
    for(LL k=;k<;k++)
    {
        f[k][]=f[k][]=inv[k][]=inv[k][]=;
        for(LL i=;i<=p[k];i++) f[k][i]=f[k][i-]*i%p[k],inv[k][i]=inv[k][p[k]%i]*(p[k]-p[k]/i)%p[k];
        for(LL i=;i<=p[k];i++) inv[k][i]=inv[k][i]*inv[k][i-]%p[k];
    }
}
LL lucas(LL n,LL m,LL op)
{
    if (m>n) return ;
    LL ans=;
    for (;m;n/=p[op],m/=p[op])
        ans=ans*C(n%p[op],m%p[op],op)%p[op];
    return ans;
}
LL INV(LL a,LL p) {return pow(a,p-,p);}
void solve(LL m)
{
    LL ans=;
    for(LL k=;k<;k++)
    {
        LL tmp=lucas(n,m,k);
        ans=(ans+tmp*(MOD/p[k])%MOD*INV(MOD/p[k],p[k])%MOD)%MOD;
    }
    b=(b+ans)%MOD;
}
int main()
{
    scanf("%lld %lld",&n,&g);
    pre();
    if(g==mod) {printf("0");return ;}
    for(LL i=;i*i<=n;i++)
        if(n%i==)
        {
            solve(i);
            if(i*i!=n) solve(n/i);
        }
    printf("%lld",pow(g,b,mod));
}