?
我們根據歐幾里得定理可以知道
(a,b)=(b,a mod b)也可以得到
(a+b,b)=(b,(a+b) mod b)=(b,a)=(a,b)
直觀點說就是兩個數a,b的gcd，和a+b,b的gcd是相等的
那么我們可以知道phi(m!)也就是與1-m!中與m!互質的數，
那么對于每個互質的數，我們加上m!，就可以得到一個新的
和m!互質的數，所以對于每個1-m!與m!互質的數
n!范圍內一共可以得到n!/m!組解，那么一共也就是phi(m!)*(n!/m!)
可以將phi(m!)用公式展開化簡，在此不再贅述
/**************************************************************
Problem:
2186
User: BLADEVIL
Language: Pascal
Result: Accepted
Time:
9524
ms
Memory:
248272
kb
****************************************************************/
//
By BLADEVIL
var
t, r :longint;
i :longint;
prime :
array
[
0
..
1000001
]
of
longint;
flag :
array
[
0
..
10000001
]
of
boolean;
fac, pi1, pi2 :
array
[
0
..
10000001
]
of
int64;
x, y :int64;
procedure
make;
var
i, j :longint;
begin
fac[
0
]:=
1
;
flag[
1
]:=
true;
for
i:=
1
to
10000000
do
fac[i]:=fac[i-
1
]*int64(i)
mod
r;
for
i:=
2
to
10000000
do
begin
if
not
flag[i]
then
begin
inc(prime[
0
]);
prime[prime[
0
]]:=
i;
end
;
for
j:=
1
to
prime[
0
]
do
begin
if
i*prime[j]>
10000000
then
break;
flag[i
*prime[j]]:=
true;
if
i
mod
prime[j]=
0
then
break;
end
;
end
;
pi1[
0
]:=
1
; pi2[
0
]:=
1
;
for
i:=
1
to
10000000
do
begin
pi1[i]:
=pi1[i-
1
];
if
not
flag[i]
then
pi1[i]:=pi1[i]*int64(i-
1
)
mod
r;
end
;
for
i:=
1
to
10000000
do
begin
pi2[i]:
=pi2[i-
1
];
if
not
flag[i]
then
pi2[i]:=pi2[i]*int64(i)
mod
r;
end
;
end
;
procedure
ex_gcd(a,b:int64);
var
z :int64;
begin
if
b=
0
then
begin
x:
=
1
; y:=
0
; exit;
end
;
ex_gcd(b,a
mod
b);
z:
=
x;
x:
=
y;
y:
=z-(a
div
b)*
y;
end
;
function
gcd(a:int64):int64;
begin
ex_gcd(a,r);
gcd:
=(x
mod
r+r)
mod
r;
end
;
procedure
main;
var
i :longint;
ans :int64;
n, m :longint;
begin
read(n,m);
ans:
=
fac[n];
ans:
=ans*pi1[m]
mod
r;
ans:
=ans*gcd(pi2[m])
mod
r;
writeln(ans);
end
;
begin
read(t,r);
make;
for
i:=
1
to
t
do
main;
end
.
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
