A
多次询问 \(l,r\)，求 \(\sum_{x=l}^r\sum_{y=x}^r a_x \otimes \gcd(a_x\sim a_y)\)，其中 $\otimes $ 是异或。
我们先拆解询问，\(Ans=\sum_{x=1}^r\sum_{y=x}^r a_x \otimes \gcd(a_x\sim a_y)-\sum_{x=1}^{l-1}\sum_{y=x}^r a_x \otimes \gcd(a_x\sim a_y)\)
然后离线处理一下。
发现 \(\gcd(a_x\sim a_y)\) 的对于所有 \(a_y\) 取值最多只有 \(\log(值域)\) 种。
可以求出 \(\gcd(a_x\sim a_y)\) 不同取值