「SDOI2010」 古代猪文 - Lucas定理+CRT

本文主要是介绍「SDOI2010」 古代猪文 - Lucas定理+CRT，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

Luogu2480

题意简述：给定$n,G$，求
$$G^{\sum _{d|n}{C}_n^d}\text{mod}999911659$$

分析

若$G\text{mod}999911659=0$，则答案为$0$。否则，可以发现，$999911659$是个质数，可以运用欧拉定理的推论：

若$gcd(a,p)=1$，则$a^b\equiv a^{b\text{mod}\varphi (p)}(\text{mod}p)$

将模数转移到指数上，变为求$\sum _{d|n}{C}_n^d\text{mod}999911658$，然后用快速幂就得到答案了。
然后这东西看着可以用Lucas定理搞，但显然999911658不是质数，用扩展Lucas的方法，将其进行质因数分解，发现$999911658=2\ast 3\ast 4679\ast 35617$，于是可以用Lucas分别求$\sum _{d|n}{C}_n^d$模其质因数，设得到的结果为$a_1,a_2,a_3,a_4$，然后再用中国剩余定理求解一下方程组：
$$\{\begin{array}{l}x\equiv a_1(\text{mod}2)\\ x\equiv a_2(\text{mod}3)\\ x\equiv a_3(\text{mod}4679)\\ x\equiv a_4(\text{mod}35617)\end{array}$$

设该方程组的最小正整数解为$x$，则答案为$G^x$。

附：欧拉定理推论的证明。
设$b=n\ast \varphi (p)+r$，其中$0\le r<\varphi (p)$，则$r=b\text{mod}\varphi (p)$。由于欧拉定理$a^{\varphi (p)}\equiv 1(\text{mod}p)$，所以$a^b\equiv a^{n\ast \varphi (p)+r}\equiv (a^{\varphi (p)}{)}^n\ast a^r\equiv a^r\equiv a^{b\text{mod}\varphi (p)}(\text{mod}p)$。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const LL P=999911659;
const LL N=100005;
LL fac[N];
LL md[5]={4,2,3,4679,35617};
LL b[5],G,n;
LL ksm(LL x,LL y,LL p) {//快速幂 x%=p;LL res=1LL;for (;y;y>>=1,x=x*x%p)if (y&1) res=res*x%p;return res;
}
void initfac(LL n,LL p) {//阶乘预处理 fac[0]=1;for (int i=1;i<=n;i++)fac[i]=fac[i-1]*i%p;
}
LL C(LL n,LL m,LL p) {//计算C(n,m)if (m>n) return 0;return (fac[n]*ksm(fac[m],p-2,p))%p*ksm(fac[n-m],p-2,p);
}
LL Lucas(LL n,LL m,LL p) {//Lucas定理C(n,m)%p=C(n/p,m/p)*C(n%p,m%p)%pif (!m) return 1;return (Lucas(n/p,m/p,p)%p*C(n%p,m%p,p)%p)%p;
}
LL Exgcd(LL a,LL b,LL&x,LL&y) {//扩展欧几里得 if (!b) {x=1,y=0;return a;}LL d=Exgcd(b,a%b,x,y),t;t=x;x=y;y=t-(a/b)*y;return d;
}
LL CRT(LL *a,LL *m,LL n) {//中国剩余定理x==ai(mod mi)LL M=1,ans=0;for (int i=1;i<=n;i++) M*=m[i];for (int i=1;i<=n;i++) {LL x,y;Exgcd(M/m[i],m[i],x,y);x=(x%m[i]+m[i])%m[i];//求逆元 ans=(ans+a[i]*x%M*M/m[i])%M;}return (ans%M+M)%M;
}
LL Solve(LL n,LL p) {LL ans=0,m=sqrt(n);initfac(N-5,p);for (LL i=1;i<=m;i++)//枚举约数 if (n%i==0) {ans+=Lucas(n,i,p);if (i*i!=n) ans+=Lucas(n,n/i,p);//去除重复的一个 }return ans;
}
int main() {scanf("%lld%lld",&n,&G);if (G%P!=0) {for (int i=1;i<=4;i++)b[i]=Solve(n,md[i]);printf("%lld",ksm(G,CRT(b,md,4),P));} else printf("0");return 0;
}

这篇关于「SDOI2010」 古代猪文 - Lucas定理+CRT的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---