百度收录网站名,手机如何制作游戏,网站不能正常显示出现后台代码,如何能去医疗网站做编辑大早上起来写题有助于醒脑#xff08;其实是昨晚没睡好/kk 正题
题目链接:https://www.luogu.com.cn/problem/P2480 题目大意
给出nnn和ggg#xff0c;求g∑d∣nCnd%999911659g^{\sum_{d|n}C_{n}^d}\% 999911659g∑d∣nCnd%999911659 解题思路
因为999911659999911659…大早上起来写题有助于醒脑其实是昨晚没睡好/kk 正题
题目链接:https://www.luogu.com.cn/problem/P2480 题目大意
给出nnn和ggg求g∑d∣nCnd%999911659g^{\sum_{d|n}C_{n}^d}\% 999911659g∑d∣nCnd%999911659 解题思路
因为999911659999911659999911659是质数根据欧拉定理我们就有g∑d∣nCnd%999911658%999911659g^{\sum_{d|n}C_n^d\% 999911658}\% 999911659g∑d∣nCnd%999911658%999911659
接下来就是要求∑d∣nCnd%999911658\sum_{d|n}C_n^d\% 999911658d∣n∑Cnd%999911658 显然nnn这么大师需要LucasLucasLucas定理的但是模数不是质数考虑拆开有9999116582∗3∗4679∗356179999116582*3*4679*356179999116582∗3∗4679∗35617。如果我们求出∑d∣nCnd\sum_{d|n}C_n^d∑d∣nCnd在这4个模数下的值我们可以用中国剩余定理 {x≡a1(mod2)x≡a2(mod3)x≡a3(mod4679)x≡a4(mod35617)\left\{\begin{matrix}x\equiv a_1(mod\ \ 2)\\x\equiv a_2(mod\ \ 3)\\x\equiv a_3(mod\ \ 4679)\\x\equiv a_4(mod\ \ 35617)\end{matrix}\right.⎩⎪⎪⎨⎪⎪⎧x≡a1(mod 2)x≡a2(mod 3)x≡a3(mod 4679)x≡a4(mod 35617) 求出xxx的解值就是∑d∣nCnd%999911658\sum_{d|n}C_n^d\% 999911658d∣n∑Cnd%999911658的值了 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll P999911658,m[4]{2,3,4679,35617},N35620;
ll n,g,ans,fac[N],a[4],M[4];
ll power(ll x,ll b,ll p){ll ans1;while(b){if(b1)ansans*x%p;xx*x%p;b1;}return ans;
}
ll C(ll n,ll m,ll p){if(nm)return 0ll;return fac[n]*power(fac[m],p-2,p)%p*power(fac[n-m],p-2,p)%p;
}
ll Lucas(ll n,ll m,ll p){if(nm)return 0ll;if(!n)return 1ll;return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
}
void Count(ll p,ll P){for(ll i1;iP;i)fac[i]fac[i-1]*i%P;for(ll i1;i*in;i)if(n%i0){(a[p]Lucas(n,i,P))%P;if(i*i!n)(a[p]Lucas(n,n/i,P))%P;}return;
}
void CRT(){for(ll i0;i4;i){M[i]P/m[i];(ansa[i]*M[i]%P*power(M[i],m[i]-2,m[i])%P)%P;}return;
}
int main()
{scanf(%lld%lld,n,g);if(g%(P1)0){printf(0);return 0;}fac[0]1;for(ll i0;i4;i)Count(i,m[i]);CRT();printf(%lld,power(g,ans,P1));return 0;
}
