【BZOJ2301】【HAOI2011】Problem b

这题的要求十分明确了

首先我们可以把询问拆成四份容斥一下

对于一个拆出来的询问\(ask(a,b,k)\)表示满足\(gcd(i,j)=k(i\in[1,a],j\in[1,b])\)的\((i,j)\)对数

也就是满足\(gcd(i,j)=1(i\in[1,a/k],j\in[1,b/k])\)的\((i,j)\)对数

用一下莫比乌斯反演就是求\(\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{d|gcd(i,j)}\mu (d)\)

也就是\(\sum_{d=1}^{min(a,b)}\left\lfloor\frac{a}{d}\right\rfloor\left\lfloor\frac{b}{d}\right\rfloor\mu (d)\)

然后\(\left\lfloor\frac{a}{d}\right\rfloor\)的取值貌似是\(O(\sqrt{n})\)级别的

所以预处理一下\(\mu(d)\)的前缀和就可以跳着搞了

说点什么

  Subscribe  
提醒