#include <bits/stdc++.h>
#define ll long long
#define ull __int128
using namespace std;
const int B = 4e7, N = 45;
ll n, ans;
ull exgcd(ull a, ull b, ull c, ull n) {
    if (!b)
        return a / c * (n + 1);

    if (a >= c || b >= c)
        return a / c * (n + 1) + b / c * n * (n + 1) / 2 + exgcd(a % c, b % c, c, n);

    ull m = (a + n * b) / c;
    return n * m - exgcd(c - a - 1, c, b, m - 1);
}
ll f[N];
void solve(ll a, ll b, ll n) {
    for (int i = 0; i <= 40; i++)
        f[i] = exgcd(a, b, (1ll << i), n);

    for (int i = 0; i < 40; i++)
        ans ^= (((f[i] - f[i + 1] * 2) & 1) << i);
}
signed main() {
    cin >> n;

    for (int i = 1; i <= min(n, 1ll * B); i++)
        ans ^= n % i;

    for (ll l = B + 1, r; l <= n; l = r + 1) {
        r = n / (n / l);
        solve(n % r, n / l, r - l);
    }

    cout << ans;
    return 0;
}

求 $n \mod 1 \oplus n \mod 2 \oplus \dots \oplus n \mod n$ 的详细题解

题目分析

给定正整数 $n$（$1 \le n \le 10^{12}$），计算异或和 $ans = (n \mod 1) \oplus (n \mod 2) \oplus \dots \oplus (n \mod n)$。
直接暴力枚举 $1 \sim n$ 计算显然不可行（$n$ 达 $10^{12}$），需结合数论分块、异或按位独立性、类欧几里得算法等数学工具优化。

核心思路

1. 异或的按位独立性

异或运算的每一位相互独立：最终结果的第 $k$ 位为 $1$，当且仅当所有 $n \mod i$ 中第 $k$ 位为 $1$ 的数的个数为奇数。
因此，可分别计算每一位 $k$（$0 \le k \le 40$，因 $2^{40} \approx 10^{12}$）的贡献，再组合得到最终答案。

2. 数论分块（整除分块）

观察到 $n \mod i = n - i \cdot \lfloor \frac{n}{i} \rfloor$。对于 $i$ 的一段区间 $[l, r]$，若 $\lfloor \frac{n}{i} \rfloor$ 恒等于 $q$（即 $q$ 为定值），则 $n \mod i = n - q \cdot i$，可批量处理该区间的异或贡献。

• 小范围 $i \in [1, B]$（$B=4 \times 10^7$）：直接暴力计算（时间可接受）。
• 大范围 $i \in [B+1, n]$：用数论分块，每块 $[l, r]$ 满足 $r = \lfloor \frac{n}{q} \rfloor$（$q = \lfloor \frac{n}{l} \rfloor$），块内 $q$ 为定值，批量计算贡献。

3. 块内异或贡献计算（solve函数）

对块 $[l, r]$，设 $q = \lfloor \frac{n}{l} \rfloor$，$m = r - l$（$i = l + t$，$t \in [0, m]$），则：
$n \mod i = n - q \cdot (l + t) = (n - q \cdot l) - q \cdot t = a - b \cdot t$，其中 $a = n \mod l$，$b = q$。
需计算异或和 $XOR_{t=0}^m (a - b \cdot t)$，转化为按位计算：对每一位 $k$，计算 $(a - b \cdot t)$ 第 $k$ 位为 $1$ 的个数的奇偶性。

4. 类欧几里得算法（exgcd函数）

第 $k$ 位为 $1$ 等价于 $\lfloor \frac{a - b \cdot t}{2^k} \rfloor$ 为奇数（因 $\lfloor \frac{x}{2^k} \rfloor$ 的二进制最低位即 $x$ 的第 $k$ 位）。
需计算 $sum = \sum_{t=0}^m \lfloor \frac{a - b \cdot t}{c} \rfloor$（$c=2^k$），其奇偶性即该位贡献。用类欧几里得算法高效计算该求和（递归降低系数规模，复杂度 $O(\log \max(a,b,c))$）。

算法步骤

1. 小范围暴力计算：$i \in [1, \min(n, B)]$，直接计算 $n \mod i$ 并异或到 $ans$。
2. 大范围分块处理：
   a. 对每个块 $[l, r]$，计算 $q = \lfloor \frac{n}{l} \rfloor$，$a = n \mod l$，$b = q$，$m = r - l$。
   b. 调用 solve(a, b, m)，计算块内异或贡献并更新 $ans$。
3. solve函数逻辑：
   a. 对每一位 $k$（$0 \le k \le 40$），用 exgcd 计算 $f[k] = \sum_{t=0}^m \lfloor \frac{a - b \cdot t}{2^k} \rfloor$。
   b. 由 $f[k] - 2 \cdot f[k+1]$ 的奇偶性判断第 $k$ 位贡献（推导见下文），更新 $ans$。
4. 输出 $ans$。

关键推导

为什么 $f[k] - 2 \cdot f[k+1]$ 的奇偶性是第 $k$ 位的贡献？

对任意整数 $x$，有：
$\lfloor \frac{x}{2^k} \rfloor = 2 \cdot \lfloor \frac{x}{2^{k+1}} \rfloor + (x \text{ 的第 } k \text{ 位})$
两边对 $t \in [0, m]$ 求和：
$\sum_{t=0}^m \lfloor \frac{a - b \cdot t}{2^k} \rfloor = 2 \cdot \sum_{t=0}^m \lfloor \frac{a - b \cdot t}{2^{k+1}} \rfloor + \sum_{t=0}^m (a - b \cdot t \text{ 的第 } k \text{ 位})$
令 $cnt_k = \sum_{t=0}^m (a - b \cdot t \text{ 的第 } k \text{ 位})$，则：
$cnt_k = f[k] - 2 \cdot f[k+1]$
$cnt_k$ 的奇偶性即第 $k$ 位对异或和的贡献（奇为 $1$，偶为 $0$）。

代码解析

1. 全局常量与变量

#include <bits/stdc++.h>
#define ll long long
#define ull __int128  // 避免溢出，用于类欧求和
using namespace std;
const int B = 4e7, N = 45;  // B：小范围暴力阈值；N：二进制最大位数（40足够）
ll n, ans;                  // ans：最终异或结果

2. 类欧几里得求和（exgcd函数）

计算 $\sum_{t=0}^n \lfloor \frac{a - b \cdot t}{c} \rfloor$（命名为exgcd因推导类似扩展欧几里得）。

ull exgcd(ull a, ull b, ull c, ull n) {
    if (!b)  // 边界：b=0，式子为a/c，求和t从0到n，共n+1项
        return a / c * (n + 1);

    // 拆分系数：当a >=c或b >=c时，分离整数部分（不影响求和奇偶性，简化递归）
    if (a >= c || b >= c)
        return a / c * (n + 1) + b / c * n * (n + 1) / 2 + exgcd(a % c, b % c, c, n);

    // 类欧核心变换：交换变量，降低系数规模
    ull m = (a + n * b) / c;  // 等价于max_t floor((a - b*t)/c)
    return n * m - exgcd(c - a - 1, c, b, m - 1);
}

3. 块内异或贡献计算（solve函数）

计算 $XOR_{t=0}^m (a - b \cdot t)$，并更新全局ans。

ll f[N];  // f[k]：sum_{t=0}^m floor((a - b*t)/2^k)
void solve(ll a, ll b, ll n) {
    // 1. 计算每一位k对应的求和f[k]
    for (int i = 0; i <= 40; i++)
        f[i] = exgcd(a, b, (1ll << i), n);  // c=2^i

    // 2. 计算每一位的贡献，异或到ans
    for (int i = 0; i <= 40; i++) {
        // cnt_k = f[i] - 2*f[i+1]，取奇偶性
        ll cnt = (f[i] - f[i+1] * 2) & 1;
        if (cnt) ans ^= (1ll << i);  // 第i位贡献为1
    }
}

4. 主函数（分块+暴力）

signed main() {
    cin >> n;

    // 第一部分：小范围i ∈ [1, min(n, B)]，直接暴力计算
    for (int i = 1; i <= min(n, 1ll * B); i++)
        ans ^= n % i;

    // 第二部分：大范围i ∈ [B+1, n]，数论分块
    for (ll l = B + 1, r; l <= n; l = r + 1) {
        ll q = n / l;          // 块内n//i = q（定值）
        r = n / q;             // 块的右边界：最大i满足n//i = q
        ll a = n % l;          // a = n mod l = 块内t=0时的rem_i
        ll b = q;              // b = q
        ll m = r - l;          // t的范围：0 ~ m（i从l到r）
        solve(a, b, m);        // 计算该块的异或贡献
    }

    cout << ans;
    return 0;
}

算法标签

• 数论分块（整除分块）
• 异或按位处理
• 类欧几里得算法
• 数学推导
• 暴力枚举（小范围优化）

复杂度分析

• 小范围暴力：$O(B)$，$B=4 \times 10^7$，时间可接受（约1~2秒）。
• 大范围分块：块数为 $O(\sqrt{n})$（因 $q = n//i$ 最多有 $2\sqrt{n}$ 个不同值），对每个块：
  • solve函数：$O(40 \times \log M)$（$M$ 为类欧递归深度，约 $\log 10^{12} = 40$）。
• 总复杂度：$O(B + \sqrt{n} \times 40 \times 40)$，对 $n=10^{12}$ 可轻松通过。