首先假设输入的是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
.
