BZOJ 2301

传送门

先贴点资料 然后跑

莫比乌斯反演

莫比乌斯函数

Orz ZYK

题目要求$x\in[a,b]\ y\in[c,d]$的结果,根据容斥原理可知其实就是求$(x\in[1,b]\ y\in[1,d])+(x\in[1,a-1]\ y\in[1,c-1])-(x\in[1,a-1]\ y\in[c,d])-(x\in[a,b]\ y\in[1,c-1])$的结果

既然是莫XXX繁衍反演,就要搞两个函数出来 (ZYK:你不证明怎么能用呢!)


$$F(d)=\sum_{i=1}^n\sum_{j=1}^m[d\mid gcd(i,j)]$$
$$f(d)=\sum_{i=1}^n\sum_{j=1}^m[d=gcd(i,j)]$$

那么
$$F(n)=\sum_{d\mid n} f(d)$$
求详细解释者请自行@ZYK1997

根据反演公式
$$f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d})$$

然后换个元$(d’=\frac{n}{d})$,得
$$f(n)=\sum_{n\mid d’}\mu(\frac{d’}{n})F(d’)$$

题目要求的东西搞定了,回过头看看$F(d)$怎么搞

$$F(d)=\sum_{i=1}^n\sum_{j=1}^m[d\mid gcd(i,j)]$$

$$F(d)=\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[1\mid gcd(i,j)]$$
(这一步我脑补了好久 = =)

$$F(d)=\lfloor\frac{n}{d}\rfloor\cdot\lfloor\frac{m}{d}\rfloor$$

$F(d)$也弄完了,下面看看怎么搞$\mu$(其实和筛法求$\varphi$的过程很相似…所以我就不讲了 具体看代码吧2333)

最后的$f(k)$大概是这样
$$f(k)=\sum_{i=1}^{\lfloor\frac{min(n,m)}{k}\rfloor}\mu(i)\lfloor\frac{n}{i\cdot k}\rfloor\lfloor\frac{m}{i\cdot k}\rfloor$$

但是只靠这一个式子会TLE BZOJ我又卡了你1min我错了QAQ

因为后面那一坨下取整在某一段区间内的值是一定的,所以把每一段搞成$\mu$在这一段的和乘上这一段的值

以上求的是$x\in[1,n]\ y\in[1,m]$的$f(k)$,这样答案就可以搞出来了

不注意int64会WA…

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_2301;
const maxn=50000;
var prime:array[1..maxn]of boolean;
sieve,mu:array[0..maxn]of longint;
n,i,a,b,c,d,k,tot:longint;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure init_mu;
var i,j:longint;
begin
fillchar(prime,sizeof(prime),true);
tot:=0;
mu[1]:=1;
for i:=2 to maxn do
begin
if prime[i] then
begin
inc(tot);
sieve[tot]:=i;
mu[i]:=-1;
end;
for j:=1 to tot do
begin
if i*sieve[j]>maxn then break;
prime[i*sieve[j]]:=false;
if i mod sieve[j]=0 then
begin
mu[i*sieve[j]]:=0;
break;
end else mu[i*sieve[j]]:=-mu[i];
end;
end;
for i:=2 to maxn do inc(mu[i],mu[i-1]);
end;
function solve(a,b:longint):int64;
var d,i,j:longint;
begin
a:=a div k;
b:=b div k;
d:=min(a,b);
solve:=0;
i:=1;
while i<=d do
begin
j:=min(a div(a div i),b div(b div i));
inc(solve,(mu[j]-mu[i-1])*int64(a div i)*int64(b div i));
i:=j+1;
end;
end;
begin
readln(n);
init_mu;
for i:=1 to n do
begin
readln(a,b,c,d,k);
writeln(solve(b,d)+solve(a-1,c-1)-solve(b,c-1)-solve(a-1,d));
end;
end.