公司做网站买服务器多少钱,门户网站功能清单,简单的介绍网站模板,厦门人才网唯一官网传送门 好吧我数学差的好像不是一点半点…… 题目求的是$G^{\sum_{d|n}C^d_n}mod\ 999911659$ 我们可以利用费马小定理$a^{k}\equiv a^{k\ mod\ (p-1)}(mod\ p)$ 然后组合数可以直接用Lucas搞 那么就做完啦 然而$p-1$并不是质数orz#xff0c;费马小定理不能用 那么我们考虑把…传送门 好吧我数学差的好像不是一点半点…… 题目求的是$G^{\sum_{d|n}C^d_n}mod\ 999911659$ 我们可以利用费马小定理$a^{k}\equiv a^{k\ mod\ (p-1)}(mod\ p)$ 然后组合数可以直接用Lucas搞 那么就做完啦 然而$p-1$并不是质数orz费马小定理不能用 那么我们考虑把$p-1$分解质数$9999116582*3*4679*35617$ 我们先用Lucas定理分别算出对这四个数取模的答案然后得到四个线性同余方程 然后直接用中国剩余定理解出答案就好了然而我并不会中国剩余定理orz 1 //minamoto2 #includecstdio3 #define ll long long4 using namespace std;5 const int mod999911658;6 ll n,G,val,fac[50005],a[4],b[]{2,3,4679,35617};7 inline ll ksm(ll x,ll y,ll p){8 ll res1;9 while(y){
10 if(y1) resres*x%p;
11 xx*x%p,y1;
12 }
13 return res;
14 }
15 inline void init(ll p){
16 fac[0]1;
17 for(int i1;ip;i)
18 fac[i]fac[i-1]*i%p;
19 }
20 inline ll C(ll n,ll m,ll p){
21 if(nm) return 0;
22 return fac[n]*ksm(fac[m],p-2,p)%p*ksm(fac[n-m],p-2,p)%p;
23 }
24 ll Lucas(ll n,ll m,ll p){
25 if(nm) return 0;if(!n) return 1;
26 return Lucas(n/p,m/p,p)*C(n%p,m%p,p)%p;
27 }
28 inline void CRT(){
29 for(int i0;i4;i)
30 val(vala[i]*(mod/b[i])%mod*ksm(mod/b[i],b[i]-2,b[i]))%mod;
31 }
32 int main(){
33 scanf(%lld%lld,n,G);
34 if(G%(mod1)0) return puts(0),0;
35 for(int k0;k4;k){
36 init(b[k]);
37 for(ll i1;i*in;i)
38 if(n%i0){
39 a[k](a[k]Lucas(n,i,b[k]))%b[k];
40 if(i*i!n) a[k](a[k]Lucas(n,n/i,b[k]))%b[k];
41 }
42 }
43 CRT();
44 printf(%lld\n,ksm(G,val,mod1));
45 return 0;
46 } 转载于:https://www.cnblogs.com/bztMinamoto/p/9725182.html
