BZOJ

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.