P2480 [SDOI2010]古代猪文（lucas定理）

题目链接:传送门

思路： 题目其实就是求 $G^{{\sum }_{d\mid n}C(n,d)}\%999911659$G∑d∣n​C(n,d)%999911659​的值，因为999911659是素数，我们我们可以用欧拉定理缩小幂次让原方程变为 $G^{{\sum }_{d\mid n}C(n,d)\%\left(999911658\right)}\%999911659$G∑d∣n​C(n,d)%(999911658)%999911659​，但是n太大，求幂次中的 ${\sum }_{d\mid n}C(n,d)\%999911658$∑d∣n​C(n,d)%999911658​的值就不太现实，所以我们可以考虑将999911658分解素因子 $2,3,4679,35617$2,3,4679,35617​的乘积，然后分别求 ${\sum }_{d\mid n}C(n,d)\%2$∑d∣n​C(n,d)%2​， ${\sum }_{d\mid n}C(n,d)\%3$∑d∣n​C(n,d)%3​， ${\sum }_{d\mid n}C(n,d)\%4679$∑d∣n​C(n,d)%4679​， ${\sum }_{d\mid n}C(n,d)\%35617$∑d∣n​C(n,d)%35617​。然后用CRT合并即可。

现在问题转化为大组合数取余小质数，此时我们可以使用 $lucas$lucas​定理：

$C(a,b)\%p=C(a\%p,b\%p)\ast C(a/p,b/p)\%p$C(a,b)%p=C(a%p,b%p)∗C(a/p,b/p)%p

就可以求出来了。

不过需要额外特判 $G$G是 $999911659$999911659的倍数的情况。

代码：

#include<bits/stdc++.h>
#define mset(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int N=1e5+100;
const int inf=0x3f3f3f3f;
ll fac[N],tf;//因子
void dps_fac(ll n)//分解n的所有因子
{
    tf=0;
    for(int i=1;i*i<=n;++i){
        if(n%i==0){
            fac[tf++]=i;
            if(n/i!=i) fac[tf++]=n/i;
        }
    }
}
ll pf[20],tp;//素因子
void dps_p(ll n)//分解n的素因子
{
    tp=0;
    for(ll i=2;i*i<=n;++i){
        while(n%i==0){
            pf[tp++]=i;
            n/=i;
        }
    }
    if(n!=1) pf[tp++]=n;
}
ll qpow(ll a,ll b,ll p)
{
    if( a <= 0) return 0;
    ll ans=1;
    while(b)
    {
        if(b&1) ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
ll f[40005];//n!%mod
void init(ll mod)
{
    f[0]=1;
    for(int i=1;i<=36000;++i) f[i]=(f[i-1]*i)%mod;
}
ll C(ll n,ll m,ll p)//要求:预处理mod p的阶乘f[]
{
    if(n<m) return 0;
    return f[n]*qpow(f[m],p-2,p)%p*qpow(f[n-m],p-2,p)%p;
}
//
ll lucas(ll n,ll m,ll p)//    C(a,b)%c的值
{

    if(n < m) return 0;
    if(!n) return 1;
    return lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
ll inv(ll a,ll p)//要求p是质数
{
    return qpow(a,p-2,p);
}
void CRT(ll w[],ll p[],int n,ll &m,ll &a)
{
    a=0,m=1;
    for(int i=0;i<n;++i) m*=p[i];
    for(int i=0;i<n;++i){
        ll t=m/p[i];
        a=(a+w[i]*t*inv(t,p[i]))%m;
    }
}
ll w[N];
void work(ll n,ll g,ll mod)
{
    //首先n的因子分解,然后mod进行质因子分解,用欧拉降幂先求 指数%(mod-1)
    dps_p(mod-1);
    dps_fac(n);
    for(int i=0;i<tp;++i){//枚举(mod-1)的每个素因子,求出来一份结果
        init(pf[i]);
        ll v=0;
        for(int j=0;j<tf;++j)
            v=(v+lucas(n,fac[j],pf[i]))%pf[i];//求出这个结果
        w[i]=v;
    }
    ll m,a;
    CRT(w,pf,tp,m,a);
    ll ans=qpow(g,a,mod);
    cout<<ans<<endl;
    //剩下用CRT合并
}
int main()
{
    ll n,g,mod=999911659ll;//2  3 4679 35617
    cin>>n>>g;
    if(g%mod==0){
        cout<<0<<endl;
        return 0;
    }
    work(n,g,mod);
    return 0;
}