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

[SDOI2010]古代猪文

题目大意：

给定 \(n,g\) ，求：

\[g^{\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}}\bmod 999911659 \]

solution：

模数是质数，有费马小定理，原式变为：

\[g^{\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 999911658}\bmod 999911659 \]

但直接通过 \(\text{Lucas}\) 定理计算组合数也不被允许，所以我们把 \(999911658\) ，分解下质因数：\(999911658=2\times 3\times 4679\times 35617\) 。
我们设 \(a_1=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 2,a_2=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 3,a_3=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 4679,a_4=\sum\limits_{i=1,i\mid n}^{n}C_{n}^{i}\bmod 35617\) 。
对于 \(g\) 的幂次 \(p\) ，有：

\[\begin{cases} p\equiv a_1 \pmod 2\\ p\equiv a_2 \pmod 3\\ p\equiv a_3 \pmod {4679}\\ p\equiv a_4 \pmod {35617} \end{cases}\]

用 \(\text{CRT}\) 求解即可。

细节处理：

  • 对于 \(g=999911659\) 要进行特判，因为此时 \(g\) 的几次幂都不可能为 \(0\) ，而此时答案显然为 \(0\) 。
代码 
#include
using namespace std;
typedef long long LL;
const int N=40000,mod=999911659,M=999911658;
int a[5],mi[5]={0,2,3,4679,35617};
int fac[N],inv[N];
inline int qpow(int x,int b,int p){
	int res=1;
	while(b){
		if(b&1) res=(LL)res*x%p;
		x=(LL)x*x%p;
		b>>=1;
	}
	return res;
}
inline void Fac(int p){
	fac[0]=1;
	for(int i=1;i<=p;i++)//实际上到 p-1 即可
		fac[i]=(LL)fac[i-1]*i%p;
}
inline void Inv(int p){
	inv[p-1]=qpow(fac[p-1],p-2,p);//需要用 fac[p-1] 往回推。
	for(int i=p-2;i>=0;i--)
		inv[i]=(LL)inv[i+1]*(i+1)%p;
}
inline int C(int n,int m,int p){
	if(n

End

A题解数学：同余数学：欧拉函数欧拉定理数学：约数数学：快速幂数学：中国剩余定理数学：组合数学

相关

洛谷P1060 java题解

【CodeForces】906 D. Power Tower 扩展欧拉定理

拓展欧拉定理漫谈

标签