P10031 Xor with Gcd 题解

T_TLucas_Yin · 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;
}