P12388 Easy Equation

 （图：某位不愿透露姓名的热心 /ˈfɜri/ 网友）

定义： $$f(n)=\sum_{i=1}^n\sum_{j=1}^n[\operatorname{popcount}(i+j)\gcd(i,j)=\max(i,j)]$$ 其中 $\operatorname{popcount}(x)$ 是 $x$ 在二进制下 $1$ 的个数，$\gcd(i,j)$ 是 $i,j$ 的最大公约数。 现在给定正整数 $n$，你需要求出 $f(1)\oplus f(2)\oplus\cdots\oplus f(n)$ 的值。其中 $\oplus$ 是按位异或。

无

无

**本题采用捆绑测试。** - Subtask 1 (10pts)：$n\le 10$。 - Subtask 2 (10pts)：$n\le 10^3$。 - Subtask 3 (20pts)：$n\le 10^5$。 - Subtask 4 (30pts)：$n\le 10^6$。 - Subtask 5 (30pts)：$n\le 10^7$。 对于全部数据，$1\le n\le 10^7$。