#GCD
这一类题大多是这样的……
给定\(a,b,k\),求\(\mathrm{gcd}(x,y)=k,1\le x\le a,1\le y\le b\)的解的组数（BZOJ 1101,BZOJ 2190）
同时有很多组变形
- 给定\(a,b,c,d,k\),求\(\mathrm{gcd}(x,y)=k,a\le x\le b,c\le y\le d\)的解的组数（BZOJ 2301）
- 给定\(a,b,c,d\),求\(\mathrm{gcd}(x,y)=\)质数\(,a\le x\le b,c\le y\le d\)的解的组数（BZOJ 2818，BZOJ 2820）
#莫比乌斯函数
\[\mu(n)=\left\{\begin{array}{ll}1 & n=1 \\(-1)^k & n=p_1p_2p_3\ldots p_k\\0 & \mathrm{others}\end{array}\right.\]利用这个东西，我们能通过筛法很快地求出\(\mu\)
\(\mu(0)\) = 1
for i := 2\(\rightarrow\)n :
if i is a prime:
for j:= 2i \(\rightarrow\) n,step = i:
j is not a prime
if \(\left\lfloor{\frac{j}{i}}\right\rfloor\ \mathrm{mod}\ i = 0\):
\(\mu(j)\)=0
else
\(\mu(j)\)=\(-\mu(\left\lfloor{\frac{j}{i}}\right\rfloor)\)
由莫比乌斯反演，我们得到：
对于给定的\(x\)，设\(F(n)\)表示满足\(\mathrm{gcd}(x,y)=1\)的数量
\[G(n)=\sum_{1\le x \le n} F\left(\frac{n}{x}\right)\]则有
\[F(n)=\sum_{1\le x\le n}\mu(n)G\left(\frac{n}{x}\right)\]然后根据和式的分配率就能得到对于\(x\in(l,r)\)的结果了
诶，上面那几题就没啥区别了囧
对于第二种变形……我再想想