【解题报告】[SDOI2010]古代猪文

题目链接

---

前言

嗯，数论全家桶，几乎能把所有学过的有关基础数论的东西都用一遍，咕了差不多 4 个月，终于打了这题

题解

读完超长的题面之后，不难发现，我们要求的是这样一个式子:
$$
\huge g^{\sum_{k|n}C_n^k}\qquad \mod 999911659
$$
很显然的，我们只需要求出上面的次幂，就可以用快速幂求解了
下面是对上面次幂的求解过程
由于模数是一个质数，我们根据欧拉公式
$$
a^k\equiv a^{k\mod \varphi(m)}\mod m\qquad(\gcd(a,m)==1)
$$
所以对于上面的次幂我们等价于求$C_n^k \mod 999911658$

我们对于 $999911658$ 分解因数之后发现，其正好是 4 个质数之积，于是我们就得到了 4 个同余方程，对于四个同余方程我们用卢卡斯定理求解后，再用中国剩余定理合并答案即可

代码

#include<stdio.h>
#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll p=999911658;
ll n,q,f[40005];
ll a[5];
ll b[5]={0,2,3,4679,35617};

inline ll ksm(ll x,ll y,ll pp){ll res=1;while(y){if(y&1)res=res*x%pp;y>>=1;x=x*x%pp;}return res;}

inline ll inv(ll x,ll pp)
{
    return ksm(x,pp-2,pp);
}

inline ll Catalan(ll x,ll y,ll pp)
{
    if(y>x)return 0;
    return f[x]*inv(f[y],pp)%pp*inv(f[x-y],pp)%pp;
}

ll Lucas(ll x,ll y,ll pp)
{
    if(x<y)return 0;
    if(!y)return 1;
    return Lucas(x/pp,y/pp,pp)*Catalan(x%pp,y%pp,pp)%pp;
}

inline ll crt(void)
{
    ll ans=0;
    for(register int i=1;i<=4;++i)
    {
        ll w=p/b[i];
        ans=(ans+a[i]*w%p*inv(w,b[i])%p)%p;
    }
    return ans;
}

signed main(void)
{
    cin>>n>>q;
    if(!(q%(p+1)))
    {
        printf("0\n");
        return 0;
    }
    f[1]=1,f[0]=1;
    for(register int j=1;j<=4;++j)
    {
        for(register int i=2;i<=39507;++i)f[i]=f[i-1]*i%b[j];
        for(register int i=1;i*i<=n;++i)
        {
            if(!(n%i))
            {
                a[j]=(a[j]+Lucas(n,i,b[j]))%b[j];
                if(i*i!=n)a[j]=(a[j]+Lucas(n,n/i,b[j]))%b[j];
            }
        }
    }
    printf("%lld\n",ksm(q,crt(),p+1));
    return 0;
}