唐氏儿学莫比乌斯反演

标签：lfloor frac gcd limits sum rfloor 反演 莫比 儿学

不会莫比乌斯反演，所以来学。

很多博客看不懂/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 \]

整除分块，启动！

标签：lfloor,frac,gcd,limits,sum,rfloor,反演,莫比,儿学
From： https://www.cnblogs.com/theshumo/p/18475010