首先假設輸入的是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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
