[NKOJP6453]求和

求 \(\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}\mu(\gcd(i,j))^2\)。

枚举 \(\gcd\)，\(\sum\limits_{d=1}^N\mu(d)^2\sum\limits_{i=1}^{\lfloor\frac N d\rfloor}\sum\limits_{j=1}^{\lfloor\frac M d\rfloor} [\gcd(i,j)=1]\)

套莫反式子，\(\sum\limits_{d=1}^N\mu(d)^2\sum\limits_{i=1}^{\lfloor\frac N d\rfloor}\sum\limits_{j=1}^{\lfloor\frac M d\rfloor}\sum\limits_{x|\gcd(i,j)}\mu(x)\)

枚举 \(\gcd\)，\(\sum\limits_{d=1}^N\mu(d)^2\sum\limits_{i=1}^{\lfloor\frac N d\rfloor}\mu(i)\lfloor\frac N {id}\rfloor\lfloor\frac M {id}\rfloor\)

设 \(T=id\)，\(\sum\limits_{i=1}^N\lfloor\frac N T\rfloor\lfloor\frac M T\rfloor\sum\limits_{d|T}\mu(d)\mu(\frac T d)^2\)

偷一个式子，\(\sum\limits_{d|T}\mu(d)\times\mu(\frac T d)^2=\mu(\sqrt T)[T\text{是完全平方数}]\)。

尝试理解一下，首先，把 \(T\) 分解质因数之后，如果最大指数大于 \(2\)，显然是 \(0\)。那么有值的指数只会是 \(1\) 或 \(2\)，所以设 \(T=a^2b\)，\(b\) 中没有平方因子。

那我们考虑把 \(\mu(d)\) 和 \(\mu(\frac T d)\) 都有值的拿出来，他们一定会平分指数为 \(2\) 的质因数（不然乘积就是 \(0\)），即 \(a|d\land a|\frac T d\)。因为 \(\mu\) 是积性函数，故提出 \(\mu(a)\)，即 \(\sum\limits_{d|T}\mu(d)\times\mu(\frac T d)^2=\mu(a)^3\sum\limits_{x|b}\mu(x)\times\mu(\frac b x)^2\)。

因为 \(b\) 中指数都是 \(1\)，所以 \(\forall x,\mu(\frac b x)^2=1\)。所以 \(\mu(a)\sum\limits_{x|b}\mu(x)=\mu(a)[b=1]=\mu(\sqrt T)[T\text{是完全平方数}]\)。