洛谷 P2480 [SDOI2010]古代猪文 题解【CRT】【欧拉定理】【Lucas定理】

点击量：238

数论综合题。

目录

题目背景

题目背景与题目无关因此省略。题目链接

题目描述

猪王国的文明源远流长，博大精深。

iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为 $N$。当然，一种语言果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。

iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的 $k$ 分之一，其中 $k$ 是 $N$ 的一个正约数（可以是 $1$ 和 $N$）。不过具体是哪 $k$ 分之一，以及 $k$ 是多少，由于历史过于久远，已经无从考证了。

iPig 觉得只要符合文献，每一种能整除 $N$ 的 $k$ 都是有可能的。他打算考虑到所有可能的 $k$。显然当 $k$ 等于某个定值时，该朝的猪文文字个数为 $\frac Nk$。然而从 $N$ 个文字中保留下 $\frac Nk$ 个的情况也是相当多的。iPig 预计，如果所有可能的 $k$ 的所有情况数加起来为 $P$ 的话，那么他研究古代文字的代价将会是 $G$ 的 $P$ 次方。

现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字，所以你只需要告诉他答案除以 $999911659$ 的余数就可以了。

输入输出格式

输入格式：

输入有且仅有一行：两个数 $N,G$，用一个空格分开。

输出格式：

输出有且仅有一行：一个数，表示答案除以 $999911659$ 的余数。

输入输出样例

输入样例#1：

4 2

输出样例#1：

2048

说明

$10\%$ 的数据中，$1\le N\le 50$；

$20\%$ 的数据中，$1\le N\le 10^3$；

$40\%$ 的数据中，$1\le N\le 10^5$；

$100\%$ 的数据中，$1\le G\le 10^9,1\le N\le 10^9$。

题解

题意即给定 $N,G$，求
$$
G^{\sum_{d|n}\mathrm C_n^d}\bmod 999911659
$$
当 $G\bot 999911659$ （二者互质）时，指数方面可以用欧拉定理化为 $\sum_{d|n}\mathrm C_n^d\bmod 999911658$。

$999911659$ 是质数，所以 $\varphi(999911659)=999911658$，当且仅当 $G=999911659$ 时不成立，此时原式恒为 $0$，注意这里要特判。

而满足 $d|n$ 的数最多只有 $O(\log n)$ 个，这样的枚举也最多只进行了 $O(\sqrt n)$ 次，问题的关键就转到了如何快速求出 $\mathrm C_n^d$ 上了。

我们知道，当模数为质数时，可以使用 Lucas 定理来做到 $O(\log p)$ 求出组合数模 $p$ 意义下的结果，且空间复杂度最小为 $O(p)$。此时既不满足模数为质数，也无法满足空间需求。

考虑质因数分解 $999911658$ 这个数字，得到 $2\times 3\times 4679\times 35617$，它的质因数的次数都是 $1$。利用这个性质我们可以做什么呢？

令 $\mathrm C_n^d\equiv x\pmod{999911658}$，由于 $999911658$ 有上面四个质因数，所以把
$$
\left\{
\begin{aligned}
x\equiv a_1&\pmod 2\\
x\equiv a_2&\pmod 3\\
x\equiv a_3&\pmod {4679}\\
x\equiv a_4&\pmod {35617}
\end{aligned}
\right.
$$
这个方程组合并，会得到 $x\equiv a\pmod{999911658}$，$a$ 就是我们要求的答案了。

而根据 Lucas 定理，上面那四个模数都是质数，所以可以求出 $a_1,a_2,a_3,a_4$，最后用 CRT 合并一下就可以了。

时间复杂度 $O(\log^2n)$。（分别是求 $d$ 的复杂度和 Lucas 定理的复杂度）

一定要特判 $G=999911658$。

Code：

#include<cstdio>
#include<cstring>
#define ll long long
ll fact[40000],inv[40000],p;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    ll g=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
ll qpow(ll x,ll y)
{
    ll ans=1;
    while(y)
    {
        if(y&1)
            ans=ans*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ans;
}
ll qmul(ll x,ll y)
{
    ll ans=0;
    if(x<0)
        x=p+x;
    if(y<0)
        y=p+y;
    while(y)
    {
        if(y&1)
            ans=(ans+x)%p;
        x=(x+x)%p;
        y>>=1;
    }
    return ans;
}
ll C(ll n,ll m)
{
    if(n<m)
        return 0;
    if(n<p&&m<p)
        return fact[n]*inv[m]%p*inv[n-m]%p;
    return C(n/p,m/p)*C(n%p,m%p)%p;
}
int d[1000],cnt=0;
ll a[5],b[5]={0,2,3,4679,35617};
int main()
{
    ll n,g,x,y;
    scanf("%lld%lld",&n,&g);
    if(g==999911659)
    {
        puts("0");
        return 0;
    }
    for(int i=1;i*i<=n;++i)
        if(n%i==0)
        {
            d[++cnt]=i;
            if(i*i!=n)
                d[++cnt]=n/i;
        }
    //先算 T%2
    for(int l=1;l<=4;++l)
    {
        p=b[l];
        fact[0]=1;
        for(int i=1;i<p;++i)
            fact[i]=fact[i-1]*i%p;
        inv[p-1]=qpow(fact[p-1],p-2);
        for(int i=p-2;i>=0;--i)
            inv[i]=inv[i+1]*(i+1)%p;
        for(int i=1;i<=cnt;++i)
            a[l]=(a[l]+C(n,d[i]))%p;
    }
    for(int i=2;i<=4;++i)
    {
        ll g=exgcd(b[i],b[i-1],x,y);
        p=b[i-1]/g;
        x=qmul(x,(a[i]-a[i-1])/g);
        p*=b[i];
        a[i]-=qmul(x,b[i]);
        a[i]=(a[i]%p+p)%p;
        b[i]=p;
    }
    p=999911659;
    printf("%lld\n",qpow(g,(a[4]%b[4]+b[4])%b[4]));
    return 0;
}