#lucas定理，乘法逆元，中国剩余定理，欧拉定理，组合数#codevs 1830 洛谷 2480 jzoj 1518 古代猪文

题目

求 g ∑ d ∣ n C n d m o d    999911659 g^{\sum_{d|n}C_n^d}\mod 999911659 g∑d∣n​Cnd​mod999911659

分析

当g是取模的数，答案为0，因为取模的数是质数，所以g，n互质。

由欧拉定理的推论可得

g ∑ d ∣ n C n d ≡ g ∑ d ∣ n C n d m o d    999911658 m o d    999911659 g^{\sum_{d|n}C_n^d}\equiv g^{\sum_{d|n}C_n^d \mod 999911658}\mod 999911659 g∑d∣n​Cnd​≡g∑d∣n​Cnd​mod999911658mod999911659

所以关键就是求出 ∑ d ∣ n C n d m o d    999911658 \sum_{d|n}C_n^d\mod 999911658 d∣n∑​Cnd​mod999911658，分解999911658的质因数得到

9999911658 = 2 ∗ 3 ∗ 4679 ∗ 35617 9999911658=2*3*4679*35617 9999911658=2∗3∗4679∗35617,所以枚举n的约数d，运用lucas定理求组合数 C n d C_n^d Cnd​

(lucas定理： C n m ≡ C n m o d    p m m o d    p ∗ C n / p m / p m o d    p ∣ 1 ≤ m ≤ n C_n^m\equiv C_{n\mod p}^{m\mod p}*C_{n/p}^{m/p} \mod p|1\leq m\leq n Cnm​≡Cnmodpmmodp​∗Cn/pm/p​modp∣1≤m≤n)

求出总和后对4个质数取模，最后用中国剩余定理找出答案。

代码

#include <cstdio>
#define mod 999911659
using namespace std;
typedef long long ll;
const ll prime[4]={2,3,4679,35617};
ll g,n,sum[4],fact[36001];
ll ksm(ll x,ll y,ll p){
	ll ans=1;
	while (y){
		if (y&1) ans=ans*x%p;
		x=x*x%p; y>>=1;
	}
	return ans;
}
ll c(ll n,ll m,ll p){if (n<m) return 0; else return fact[n]*ksm(fact[n-m]*fact[m],p-2,p)%p;}//乘法逆元计算组合数
ll lucas(ll n,ll m,ll p){if (!m) return 1; else return c(n%p,m%p,p)*lucas(n/p,m/p,p)%p;}
ll getx(){
	ll ans=0; 
	for (int i=0;i<4;i++){
		ll tmp=(mod-1)/prime[i];
		ans=(ans+sum[i]*tmp%(mod-1)*ksm(tmp,prime[i]-2,prime[i])%(mod-1))%(mod-1);//乘法逆元
	}
	return ans;
}
int main(){
	scanf("%lld%lld",&n,&g);
	if (g==mod) return !puts("0");
	for (ll i=0;i<4;i++){
		fact[0]=1;
		for (ll j=1;j<=prime[i];j++) fact[j]=fact[j-1]*j%prime[i];
		for (ll d=1;d*d<=n;d++)
		if (n%d==0){
			sum[i]=(sum[i]+lucas(n,d,prime[i]))%prime[i];//求出总和
			if (d*d==n) continue;
			sum[i]=(sum[i]+lucas(n,n/d,prime[i]))%prime[i];//若不是完全平方数，那么计算相同的总和
		}
	}
	return !printf("%lld",ksm(g,getx(),mod));
}