$异或约数和$异或约数和

$最初想法$最初想法

$[1,x]$[1,x] 内含有 $x$x 这个约数的数个数为 $cnt=\lfloor \frac{N}{x}\rfloor$cnt=⌊xN​⌋,
当 $cnt$cnt 为偶数时, 贡献为 $0$0, 当 $cnt$cnt 为奇数时, 对整体答案贡献为 异或 $x$x,
枚举 $x\in [1,N]$x∈[1,N] 直接计算贡献, 复杂度 $O\left(N\right)$O(N) .
用 整除分块 加上类似 这里 的方法可以优化到 $O\left(\sqrt{N}logN\right)$O(N ​logN), 但是仍然不能 $AC$AC.

$正解部分$正解部分

有一个规律, 设 $g\left(x\right)$g(x) 为 $[1,x]$[1,x] 内的异或和, 则

$g\left(x\right)=\{\begin{array}{c}0奇数\\ xelse\end{array}+\{\begin{array}{c}1\lceil \frac{N}{2}\rceil 为奇数\\ 0else\end{array}$g(x)={0    奇数x   else​+{1    ⌈2N​⌉为奇数0    else​

于是前面需要 $O\left(logN\right)$O(logN) 计算的只需要 $O\left(1\right)$O(1) 了, 总体复杂度 $O\left(\sqrt{N}\right)$O(N ​) , 可以 $AC$AC .

$实现部分$实现部分

没什么好说的 …

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

ll N;
ll Ans;

ll Sum(ll x){
        if(!x) return 0;
        ll s_1, s_2;
        if(x & 1) s_1 = 0;
        else s_1 = x;
        ll tmp = (N-1)/x + 1;
        if(tmp & 1) s_2 = 1;
        else s_2 = 0;
        return s_1 + s_2;
}

int main(){
	scanf("%lld", &N);
	for(reg ll l = 1, r; l <= N; l = r+1){
		r = N/(N/l);
		if((N/l & 1) == 0) continue ;
		Ans ^= Sum(r) ^ Sum(l-1);
	}
        printf("%lld\n", Ans);
	return 0;
}