唐氏儿学莫比乌斯反演
不会莫比乌斯反演，所以来学。
很多博客看不懂/kk。
题目
P 2522
\[\sum\limits^b_{i=a}\sum\limits_{j=c}^{d}[\gcd(i,j)=k]
\]
容斥，
\[\sum\limits^b_{i=a} \sum\limits_{j=c}^{d} [\gcd(i,j)=k]= \sum\limits^b_{i=1}\sum\limits_{j=1}^{d}[\gcd(i,j)=k]- \sum\limits^b_{i=1}\sum\limits_{j=1}^{c-1}[\gcd(i,j)=k]-\newline
\sum\limits^{a-1}_{i=1}\sum\limits_{j=1}^{d}[\gcd(i,j)=k]+ \sum\limits^{a-1}_{i=1}\sum\limits_{j=1}^{c-1}[\gcd(i,j)=k]\]
所以只要能查
\[ \sum\limits^x_{i=1}\sum\limits_{j=1}^{y}[\gcd(i,j)=k]
\]
就行了。不妨令 \(x\leq y\)。
经典同时除以 \(k\) 。化为
\[\sum\limits_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{y}{k}\rfloor}[\gcd(i,j)=1]
\]
运用莫比乌斯反演。
\[\sum\limits_{d\mid \gcd(i,j)} \mu(d) = [\gcd(i,j)=1]
\]
\[\sum\limits_{i=1}^{\lfloor\frac{x}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{y}{k}\rfloor}\sum\limits_{d\mid \gcd(i,j)} \mu(d)
\]
枚举 \(d\)
\[\sum^{\lfloor\frac{x}{k}\rfloor}_{d=1}\sum^{\lfloor\frac{x}{k}\rfloor}_{i=1}\sum^{\lfloor\frac{y}{k}\rfloor}_{j=1}[d\mid i] [d \mid j] \mu(d)
\]
\(\mu(d)\) 显然可以提前。
\[\sum^{\lfloor\frac{x}{k}\rfloor}_{d=1}\mu(d) \sum^{\lfloor\frac{x}{k}\rfloor}_{i=1}\sum^{\lfloor\frac{y}{k}\rfloor}_{j=1}[d\mid i] [d \mid j]
\]
换一下位置。
\[\sum^{\lfloor\frac{x}{k}\rfloor}_{d=1}\mu(d) \sum^{\lfloor\frac{x}{k}\rfloor}_{i=1}[d\mid i]\sum^{\lfloor\frac{y}{k}\rfloor}_{j=1} [d \mid j]
\]
然后我们可以发现
\[\sum^{\lfloor\frac{x}{k}\rfloor}_{i=1}[d\mid i]
\]
这个式子不就是求 \(1\) 到 \(\lfloor\frac{x}{k}\rfloor\) 的所有数中能被 \(d\) 整除的数的个数吗，化简一下，就是 \(\lfloor\frac{\lfloor\frac{x}{k}\rfloor}{d}\rfloor\) 。
所以上上式就可以化简成
\[\sum^{\lfloor\frac{x}{k}\rfloor}_{d=1}\mu(d) \cdot\lfloor\frac{\lfloor\frac{x}{k}\rfloor}{d}\rfloor\cdot\lfloor\frac{\lfloor\frac{y}{k}\rfloor}{d}\rfloor
\]
整除分块，启动！