BZOJ

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.