题解 P2480 【[SDOI2010]古代猪文】

· · 题解

这是一道数论全家桶！！

前言：这是一道十分有趣的数论题！！可以说是基础数论全家桶！！

虽然钟长者说，见到输入几个数，输出一个数，应该果断选择一种古老而又优秀的算法——打表！！！但是还是果断的去莽这个题

内置数论知识：欧拉-费马定理，Lucas定理，中国剩余定理(CRT)。这可真是一道“优美”基础数论全家桶！！！！

话不多说，现在开始 口胡 ta!\ !\ !

当然这题面又臭又长，显然需要把题面化简一下子啦！！！

存在一个整数N，对于每一个约数d，(d|N或N\ mod\ d=0)，求C^{d}_{n}\ mod\ \ 999911659。

最终的答案就是：

G^{\sum_{d|n}{C^{d}_{n}}}mod\ 999911659

首先检验一下999911659是一个质数，并没有什么问题！！

盲猜这个指数非常大，所以不如先来考虑一波欧拉定理！

欧拉定理

当∀a,m\in \mathbb{Z}且gcd(a,m)=1，a^{\varphi(m)}\equiv1\ (mod\ m)

这里的\varphi(m)，是数论下的欧拉函数。即\varphi(m)=\sum^{m-1}_{i=1}{gcd(i,m)=1}。显然当m是一个质数时，\varphi(m)=m-1。

∀a,m\in \mathbb{Z}$且$gcd(a,m)=1$，$a^b\equiv a^{b\ mod\ \varphi(m)}\ (mod\ m)

欧拉定理的正确性，弱弱的本人也不会，还请各位爷去问“无所不知无所不能”的度娘！！

$$a^b\equiv \begin{cases} a^{b\ mod\ \varphi(m)}&gcd(a,m)=1\\ a^b&b<\varphi(m)\\ a^{b\ mod\ \varphi(m)+\varphi(m)}&b\geq \varphi(m) \end{cases}\ (mod\ m)$$ 证明这种东西当然还得依靠度娘了！！！ 而**费马小定理**是欧拉定理的一个推论，$∀a,m\in \mathbb{Z}$且$gcd(a,m)=1$且$m\in Prime$，$a^{m-1}\equiv 1(mod\ m)$。 毕竟当$m\in Prime$时，$\varphi(m)=m-1$。那么根据欧拉定理，于是~~~嘤嘤嘤~~ ------------ ------------ 我么不妨对原式$G^{\sum_{d|n}{C^{d}_{n}}}mod\ 999911659$采用一波欧拉定理。 可得到： $$G^{\sum_{d|n}{C^{d}_{n}}}\equiv\ G^{\sum_{d|n}C^{d}_{n}\ mod\ 999911658}\ (mod\ 999911659)$$ 那这样的话，我们现在要求的式子变成了$G^{\sum_{d|n}C^{d}_{n}\ mod\ 999911658}\ mod\ 999911659$。 很显然的一个步骤在这摆着，对于这个底数$G$和最终取模数$mod\ 999911659$，我们可以直接用费马小定理求出，那么关键步骤呈现在我们的眼前！！！ **求出：**$\sum_{d|n}{C^{d}_{n}\ mod\ 999911658}$！！！ 首先$999911658$不是一个质数，暴力求组合数之后费马小定理肯定行不通！！ 根据取模的性质，我们不妨进行一波下面的显然操作求：$\sum_{d|n}{(C^{d}_{n}\ mod\ 999911658)\ mod\ 999911658}

废话，这太显然了！！！！

但是这样我们发现，我们的问题变成了一个组合数取模问题！！！

想想组合数取模能怎么做？？

Lucas定理？？？

**扩展$Lucas$定理？？？** 似乎是可以的，但是好难好麻烦，还需要$Exgcd$和$ExCRT$！！！ **中国剩余定理$(CRT)$？？?** 我们先计算一波$999911658$的质因数！！$Emm$，很好$999911658=2\times3\times4697\times35617$四个，那么显然可用中国剩余定理！！ ------------ ------------ ### 中国剩余定理 求解同于方程组 $$(S)\begin{cases} x\equiv a_{1}&(mod\ m_{1})\\ x\equiv a_{2}&(mod\ m_{2})\\ x\equiv a_{3}&(mod\ m_{3})\\ &\vdots\\ x\equiv a_{k}&(mod\ m_{k})\\ \end{cases}$$ 其中$m_{1},m_{2},m_{3},\ldots\ \ldots,m_{k}$为两两互质的整数，求x的解。 **定理:** 令$M=\Pi^{k}_{i=1}{m_{i}}$，即$M$是所有$m_{i}$的最小公倍数。 设$M_{i}=M/m_{i}$，$∀\ i\in \{1,2,3,\ldots,k\}$是除了$m_{i}$以外的$n-1$个数的乘积。 设$t_{i}$为$M_{i}$模$m_{i}$意义下的逆元。即$M_{i}t_{i}\equiv1\ (mod\ m_{i}),∀\ i\in \{1,2,3,\ldots,k\}$。 那么方程组$(S)$的通解形式为： $x=a_{1}t_{1}M_{1}+a_{2}t_{2}M_{2}+a_{3}t_{3}M_{3}+\ldots+a_{k}t_{k}M_{k}+TM,T\in\mathbb{Z}

即：x=\sum^{n}_{i=1}{a_{i}t_{i}M_{i}}+TM,T\in\mathbb{Z}

那么在模M的意义下，方程组(S)有且仅有一个解，即x=(\sum_{i=1}^{n}{a_{i}t_{i}M_{i}})modM

对于证明，本人太多，请各位神仙前往度娘！！

那么我们显然可以，将\sum_{d|n}C^{d}_{n}分别对999911658的四个质因数取模，构建同余方程组，求出在模通解999911658的通解t，那么t=\sum_{d|n}C^{d}_{n}mod\ 999911658。

最终答案即为：G^{t}\ mod999911659。

那么构建出来的同余方程组长什么样子呢？？？

x\equiv \sum_{d|n}C^{d}_{n}&(mod\ 2)\\ x\equiv \sum_{d|n}C^{d}_{n}&(mod\ 3)\\ x\equiv \sum_{d|n}C^{d}_{n}&(mod\ 4679)\\ x\equiv \sum_{d|n}C^{d}_{n}&(mod\ 35617)\\ \end{cases}

当然对于每一个同余方程可以先用取模的性质化简化简！！！

在这里我们发现，对于每个组合数C_{n}^{d}取模的四个数2,3,4679,35617，都很小而且都是质数，那么我们可以采用Lucas定理来对组合数取模。

Lucas定理

C_{n}^{m}mod\ p=C^{m/p}_{n/p}\times C^{m\ mod\ p}_{n\ mod\ p}

当且仅当p是一个小质数！！

弱弱的本人根本不会证明，还请各位大神询问度娘

中间还存在一些小细节，比如求组合数可用民间的提前预处理每个数的阶乘和每个数阶乘的逆元，然后每次求组合数变成了一次O(1)操作！！！

所以这篇鬼畜的古代猪文就能告一段落了，这可真是一道数论好题。费马-欧拉定理，Lucas定理，中国剩余定理。基本可以说，这是一道取模方面的数论全家桶！！！！

Code Below

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
#define Mod 999911659
#define mod 999911658
#define maxn 40005
typedef long long ll;
ll n,g;
ll d[maxn],tot;
ll p[10],cnt;

inline ll qpow(ll a,ll k,ll p)
{
    ll res=1;
    while(k)
    {
        if(k&1) res=(res*a)%p;
        a=(a*a)%p;
        k>>=1;
    }
    return res%p;
}

ll fac[maxn],inv[maxn];
inline void init(ll p)
{
    fac[0]=1;
    for(register int i=1;i<p;i++)
        fac[i]=fac[i-1]*i%p;
    inv[p]=0;
    inv[p-1]=qpow(fac[p-1],p-2,p);
    for(register int i=p-2;i>=0;i--)
        inv[i]=inv[i+1]*(i+1)%p;
}

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

inline ll Lucas(ll n,ll m,ll p)
{
    if(m==0) return 1;
    return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}

ll a[10];
inline void calc(int x)
{
    init(p[x]);
    for(register int i=1;i<=tot;i++)
        a[x]=(a[x]+Lucas(n,d[i],p[x]))%p[x];
}

inline ll CRT()
{
    ll ans=0;
    for(register int i=1;i<=cnt;i++)
    {
        ll M=mod/p[i],t=qpow(M,p[i]-2,p[i]);
        ans=(ans+a[i]%mod*t%mod*M%mod)%mod;
    }
    return (ans+mod)%mod;
}

int main()
{
    scanf("%lld%lld",&n,&g);
    if(g%Mod==0)
    {
        printf("0\n");
        return 0;
    }
    ll t=mod;
    for(register int i=2;i*i<=mod;i++)
    {
        if(t%i==0)
        {
            p[++cnt]=i;
            while(t%i==0) t=t/i;
        }
    }
    if(t!=1) p[++cnt]=t;
    for(register int i=1;i*i<=n;i++)
    {
        if(n%i==0)
        {
            d[++tot]=i;
            if(i*i!=n) d[++tot]=n/i;
        }
    }
    for(register int i=1;i<=cnt;i++) calc(i);
    printf("%lld",qpow(g,CRT(),Mod));
    return 0;
}