【题解】古代猪文

\(\textrm{luogu P2480 [SDOI2010]古代猪文}\)

所以说嘛，我现在才刚入数论的门。

简要题意：

求 \(\large g^{\sum_{d \mid n}\binom{n}{d}}\) 在模 \(999911659\) 意义下的值。（以下简记为 \(mod\)）

1. 欧拉定理

检测到 \(mod\) 为素数，于是有 \(\gcd(g,mod) = 1\)，可以考虑使用欧拉定理。

欧拉定理：

\[\gcd(a,n) = 1 \implies a^n \equiv a^{n \bmod {\varphi(n)}} \pmod n \]

由于 \(mod\) 为素数，故 \(\varphi(mod) = mod-1\)。

于是原题等价于求解 \(g^{\sum_{d \mid n}\binom{n}{d} \bmod {mod-1}} \bmod mod\)。

2. 卢卡斯定理

现在发现求 \(\binom{n}{d}\) 时肯定不能直接 \(\mathcal{O}(n)\) 求，不然就爆了。

尝试卢卡斯定理：

\[p \in prime \implies \binom{n}{m} \equiv \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p \right\rfloor} \times \binom{n \bmod p}{m \bmod p} \pmod p \]

3. 中国剩余定理

发现 \(mod-1 = 999911658\) 有点大了不是？何况也不是质数，总不能打一份扩展卢卡斯罢。

尝试唯一分解：\(999911658 = 2 \times 3 \times 4679 \times 35617\)。

所以我们先求出 \(\sum_{d \mid n}\binom{n}{d}\) 在模 \(2,3,4679,35617\) 意义下的值 \(a_i,a_2,a_3,a_4\)。

最后用中国剩余定理：

合并成其在模 \(999911658\) 意义下的值。

对了，记得防爆 long long。

#include <iostream>
typedef long long llt;
const llt mod = 999911659;
const int lmod[4] = {2,3,4679,35617};
llt quick_multi(llt _a,llt n,llt p) {
	llt _res = 0ll;
	while(n) {
		if(n&1) {
			_res += _a;
			if(_res >= p) 
				_res -= p;
		}
		_a <<= 1;
		if(_a >= p) 
			_a -= p;
		n >>= 1;
	}
	return _res;
}
int quick_pow(int _a,int n,int p) {
	int _res = 1;
	while(n) {
		if(n&1) 
			_res = 1ll*_res*_a%p;
		_a = 1ll*_a*_a%p;
		n >>= 1;
	}
	return _res;
}
llt defend_pow(llt _a,llt n,llt p) {
	llt _res = 1ll;
	while(n) {
		if(n&1) 
			_res = quick_multi(_res,_a,p);
		_a = quick_multi(_a,_a,p);
		n >>= 1;
	}
	return _res;
}
int fact[35620], inv[35620];
int a[4];
void init(int p) {
	fact[0] = inv[0] = 1;
	for(int i = 1;i < p;++i) 
		fact[i] = 1ll*fact[i-1]*i%p;
	inv[p-1] = quick_pow(fact[p-1],p-2,p);
	for(int i = p-2;i >= 1;--i) 
		inv[i] = 1ll*inv[i+1]*(i+1)%p;
}
int C(int n,int m,int p) {
	if(n < m||n < 0||m < 0) 
		return 0;
	return 1ll*fact[n]*inv[m]%p*inv[n-m]%p;
}
int Lucas(int n,int m,int p) {
	if(n < m) 
		return 0;
	if(!n) 
		return 1;
	return 1ll*Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
llt ans;
void CRT() {
	for(int i = 0;i < 4;++i) 
		ans = (ans+a[i]*((mod-1)/lmod[i])%(mod-1)*quick_pow(mod/lmod[i],lmod[i]-2,lmod[i]))%(mod-1);
}
int n, g;
int main() {
	scanf("%d %d",&n,&g);
	if(!(g%mod)) {
		printf("0\n");
		return 0;
	}
	for(int i = 0;i < 4;++i) {
		init(lmod[i]);
		int d = 1;
		for(;d*d < n;++d) 
			if(!(n%d)) {
				a[i] += Lucas(n,d,lmod[i])+Lucas(n,n/d,lmod[i]);
				while(a[i] >= lmod[i]) 
					a[i] -= lmod[i];
			}
		if(d*d == n) {
			a[i] += Lucas(n,d,lmod[i]);
			if(a[i] >= lmod[i]) 
				a[i] -= lmod[i];
		}
	}
	CRT();
	printf("%lld\n",defend_pow(g,ans,mod));
	return 0;
}

原文地址：http://www.cnblogs.com/bikuhiku/p/SDOI2010-gudaizhuwen-sol.html