我们根据欧几里得定理可以知道
(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
.
