洛谷2480 [SDOI2010]古代猪文

题意

定义

$$P=\sum_{i-1}^n i|n\ C_n^i$$

求

$$G^P\mod 999911659$$

其中 $N,P\le 10^{9}$ 。

题解

由拓展欧拉定理得

$$G^P\equiv G^{P\mod \varphi(999911659)} \pmod {999911659}$$

因为 $999911659$ 是质数，所以

$$\varphi(999911659)=999911658$$

所以原题化为求

$$G^{P\mod 999911658}\pmod {999911659}$$

先求 $P\mod 999911658$ ，$P$ 中有个组合数，考虑 $\text{Lucas}$ ，但模数过大且不是质数，显然不能直接做。

考虑对 $999911658$ 进行分解：

$$999911658=2\times 3\times 4679\times 35617$$

那么可以对每个模数 $m_i$ 求出一个 $A_i$ ，然后用 $\text{CRT}$ 合并即可得到 $P$ 。

最后用快速幂得到 $G^P\mod 999911659$ 即可。

需要注意的是当 $G=999911659,P=0$ 时需要特判，我直接特判在快速幂函数里了。

#include<bits/stdc++.h>
#define ll long long
#define ha 999911659

using namespace std;

inline ll read()
{
    char ch=getchar();
    ll f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

const ll M=ha-1;
ll n,g,A[5],m[5]={0,2,3,4679,35617},fac[100005];

inline ll qpow(ll x,ll y,ll mod)
{
    if (x%mod==0) return 0;
    ll ans=1;
    while (y)
    {
        if (y&1) ans=ans*x%mod;
        y>>=1;
        x=x*x%mod;
    }
    return ans%mod;
}

inline ll inv(ll x,ll mod) { return qpow(x,mod-2,mod); }

inline ll C(ll n,ll m,ll mod)
{
    if (m>n) return 0;
    return fac[n]*(inv(fac[m],mod)*inv(fac[n-m],mod)%mod)%mod;
}

inline ll lucas(ll n,ll m,ll mod)
{
    if (!m) return 1;
    return lucas(n/mod,m/mod,mod)*C(n%mod,m%mod,mod)%mod;
}

inline ll crt()
{
    ll ans=0;
    for (ll i=1;i<=4;i++)
    {
        ll Mi=M/m[i];
        ans=(ans+(Mi*inv(Mi,m[i])%M*A[i])%M)%M;
    }
    ans=(ans+M)%M;
    return ans;
}

inline void get_fac(ll x)
{
    fac[0]=fac[1]=1;
    for (ll i=2;i<=x;i++) fac[i]=fac[i-1]*i%x;
}

signed main()
{
    n=read(); g=read();
    ll sqn=sqrt(n);
    for (ll i=1;i<=4;i++)
    {
        get_fac(m[i]);
        for (ll j=1;j<=sqn;j++)
        {
            if (n%j) continue;
            A[i]=(A[i]+lucas(n,j,m[i]))%m[i];
            if (j*j==n) continue;
            A[i]=(A[i]+lucas(n,n/j,m[i]))%m[i];
        }
    }
    return !printf("%lld",qpow(g,crt(),ha));
}