BZOJ 2186

传送门

首先,
$\varphi(x)=x\times\frac{p-1}{p}(p\mid x且p为质数)$

也就是对于$x$的每个质因数$p$,去掉$[1,x]$中$p$的$x\times\frac{1}{p}$个倍数

那么题目求的就是$n!\times\frac{p-1}{p}(p\mid m!且p为质数)$

也就是$n!\times\frac{p-1}{p}(p\mid m且p为质数)$

$n!\times(p-1)\times p^{-1}(p\mid m且p为质数,p^{-1}为p的逆元)$

那么预处理阶乘并拿扩展欧几里得找逆元就行了


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
program bzoj_2186;
const max=10000000;
var sieve,pre,fac,inv:array[0..max]of longint;
prime:array[1..max]of boolean;
t,n,m,r,x,y,tot:longint;
procedure exgcd(a,b:longint);
var t:longint;
begin
if b=0 then
begin
x:=1;
y:=0;
exit;
end;
exgcd(b,a mod b);
t:=x;
x:=y;
y:=t-(a div b)*y;
end;
procedure init_sieve;
var i,j:longint;
begin
fillchar(prime,sizeof(prime),true);
tot:=0;
for i:=2 to max do
begin
if prime[i] then
begin
inc(tot);
sieve[tot]:=i;
exgcd(i,r);
inv[i]:=(x mod r+r)mod r;
end;
for j:=1 to tot do
begin
if i*sieve[j]>max then break;
prime[i*sieve[j]]:=false;
inv[i*sieve[j]]:=int64(inv[i])*int64(inv[sieve[j]]) mod r;
if i mod sieve[j]=0 then break;
end;
end;
end;
procedure init;
var i:longint;
begin
fac[1]:=1;
for i:=2 to max do fac[i]:=int64(fac[i-1])*int64(i) mod r;
init_sieve;
pre[1]:=1;
for i:=2 to max do if prime[i] then pre[i]:=(int64(pre[i-1])*int64(i-1) mod r)*int64(inv[i]) mod r else pre[i]:=pre[i-1];
end;
begin
readln(t,r);
init;
for t:=1 to t do
begin
readln(n,m);
writeln(int64(fac[n])*int64(pre[m]) mod r);
end;
end.