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