自动搬运

查看原文

来自洛谷，原作者为

	T_TLucas_Yin 周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上线周末上

搬运于2025-08-24 22:54:02，当前版本为作者最后更新于2024-01-01 10:36:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意：给定 $n$ ，求出 $n$ 与 $1$ 到 $n$ 中所有数的最大公约数的异或和。

看到数据范围，很容易发现这是个典型的结论题。所以直接开始找规律。

对于求最大公约数，有一种方法叫做更相减损术。其中用到了这样一条规律：

改一下字母就可得

我们又知道，异或和运算满足 $a \oplus b \oplus c = a \oplus c \oplus b$ 和 $a \oplus a = 0$。

也就是说，对于所有 $1\le i < n$，我们可以把每一对 $\gcd(i,n)$ 和 $\gcd(n-i,n)$ 放到一起，这样，它们的异或和就会抵消为 $0$。

接下来看整个式子。若 $n$ 为奇数，则两两抵消后，会剩下 $\gcd(n,n)$ ，也就是 $n$ 。由于除此之外整个式子都为 $0$，所以最终的结果就是 $n$。

若 $n$ 为偶数，则两两抵消后，会剩下 $\gcd(\frac n 2,n)$ 和 $\gcd(n,n)$ 两项，它们的值刚好分别为 $\frac n 2$ 和 $n$ ，因此最终的结果就是它们的异或和。

#include<bits/stdc++.h>
using namespace std;
long long t,n;
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        if(n&1) printf("%lld\n",n);// n&1就是n%2==1
        else printf("%lld\n",(n/2)^n);
    }
    return 0;
}