首先假設輸入的是n,m
我們就是要求m^(Σ(c(n,i) i|n)) mod p
那么根據費馬小定理,上式等于
m^(Σ(c(n,i) i|n) mod ?(p-1)) mod p
那么問題的關鍵就是求?Σ(c(n,i) i|n) mod ?(p-1)了
那么如果P是素數的話,我們可以用lucas定理來快速求出來組合數,這道題的p-1是
非素數,那么我們分解質因數pi,假設c(n,i) i|n為X,那我們求出來X mod pi=ai,這個是
符合lucas定理的,那么我們可以得到質因子數個式子(本題有4個質因子),然后我們用
中國剩余定理合并這4個式子就行了
/************************************************************** ????Problem: 1951 ????User: BLADEVIL ????Language: Pascal ????Result: Accepted ????Time: 108 ms ????Memory: 540 kb ****************************************************************/ ? // By BLADEVIL const ????d39???????????????????? = 999911659 ; ????pp????????????????????? : array [ 1 .. 4 ] of longint=( 2 , 3 , 4679 , 35617 ); ????? var ????n, m, k???????????????? :int64; ????cc????????????????????? :int64; ????a?????????????????????? : array [ 0 .. 10 ] of int64; ????i?????????????????????? :longint; ????fac???????????????????? : array [ 0 .. 40000 ] of int64; ????? function ex_gcd(a,b:int64):int64; var ????z?????????????????????? :int64; begin ???? if b= 0 then ???? begin ????????ex_gcd: = 1 ; ????????cc: = 0 ; ????????exit; ???? end else ???? begin ????????z: =ex_gcd(b,a mod b); ????????ex_gcd: = cc; ????????cc: =z-(a div b)* cc; ???? end ; end ;??? ? function gcd(a,p:int64):int64; begin ????gcd: = ex_gcd(a,p); ????gcd: =(gcd mod p+p) mod p; end ; ????? function combine(a,b,p:int64):int64; var ????ans1, ans2????????????? :int64; ????i?????????????????????? :longint; begin ????ans1: =fac[a] mod p; ????ans2: =(fac[a-b]*fac[b]) mod p; ????ans2: = gcd(ans2,p); ????combine: =ans1*ans2 mod p; end ; ????? function lucas(x,y,p:int64):int64; var ????a, b??????????????????? :int64; begin ???? if y= 0 then exit( 1 ); ????a: =x mod p; ????b: =y mod p; ???? if a<b then exit( 0 ) else lucas:=lucas(x div p,y div p,p)* combine(a,b,p); end ;??? ? function crt:int64; var ????i?????????????????????? :longint; begin ????crt: = 0 ; ???? for i:= 1 to 4 do ????????crt: =(crt+a[i]*((d39- 1 ) div pp[i])*gcd((d39- 1 ) div pp[i],pp[i])) mod (d39- 1 ); end ; ? function get(x:int64):int64; var ????i, j??????????????????? :longint; begin ???????? for i:= 1 to trunc(sqrt(x)) do ???????? begin ???????????? if x mod i= 0 then ???????????? begin ???????????????? for j:= 1 to 4 do ???????????????? begin ????????????????????a[j]: =(a[j]+lucas(x,i,pp[j])) mod pp[j]; ???????????????????? if x div i<>i then a[j]:=(a[j]+lucas(x,x div i,pp[j])) mod pp[j]; ???????????????? end ; ???????????? end ; ???????? end ; ????get: = crt; end ; ? function mi(n,k,p:int64):int64; var ????sum???????????????????? :int64; begin ????mi: = 1 ; ????sum: = n; ???? while k<> 0 do ???? begin ???????? if k mod 2 = 1 then mi:=mi*sum mod p; ????????sum: =sum*sum mod p; ????????k: =k div 2 ; ???? end ; end ; ? begin ????fac[ 0 ]:= 1 ; ???? for i:= 1 to pp[ 4 ] do fac[i]:=fac[i- 1 ]*int64(i) mod (d39- 1 ); ????read(n,m); ???? if m mod d39= 0 then ???? begin ????????writeln( 0 ); ????????halt; ???? end ; ????k: = get(n); ????writeln(mi(m,k,d39)); end .
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
