标签：frac gcd limits 闲话 varphi bigotimes 开始 这件

题外话

Radiant 真的是好好听！

正文

推一个弱智式子。

\[\bigotimes_{i=1}^n\gcd(i,n) \]

（\(\bigotimes\) 是异或和）

\[\bigotimes\limits_{i=1}^n\sum\limits_{d=1}^nd[\gcd(i,n)=d] \]

\[\bigotimes\limits_{d|n}d\bigotimes\limits_{i=1}^n[\gcd(i,n)=d] \]

\[\bigotimes\limits_{d|n}d\bigotimes\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1] \]

\[\bigotimes\limits_{d|n}d[\varphi(\frac{n}{d})\nmid2] \]

显然，\(\varphi(n)\) 只有在小于等于 \(2\) 的情况下为奇数。所以答案就是：

\[n\otimes (\frac{n}{2}[n|2]) \]

标签：frac,gcd,limits,闲话,varphi,bigotimes,开始,这件
From： https://www.cnblogs.com/wdgm4/p/17749182.html