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

作者: wjyyy 分类: 中国剩余定理,数学,欧拉函数,组合数学,解题报告 发布时间: 2019-03-22 21:38

点击量:82

数论综合题。

题目背景

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

题目描述

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

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;
}

说点什么

avatar
  Subscribe  
提醒
/* */