题意分析

题目要求计算等差数列 x, x+z, x+2z, ..., x+kz（其中 x+kz ≤ y）的异或和。异或运算的规则是相同位为0，不同位为1。直接遍历数列中的每个数进行异或会超时（x, y, z可达2^32），因此需要高效算法。

解题思路

核心观察

1. 按位处理：异或运算的每一位相互独立，因此可以逐位计算数列中所有数的第i位的异或结果。
2. 前缀和转化：第i位的异或结果为1当且仅当该位为1的数的个数为奇数。因此需要统计数列中第i位为1的数的个数。
3. 数论分块优化：使用类欧几里得算法（函数f）高效计算满足条件的数的个数。

算法步骤

1. 确定数列范围：计算项数 n = (y-x)/z，数列包含 x, x+z, ..., x+n*z。
2. 逐位统计：对于每一位i（0 ≤ i ≤ 34），统计数列中第i位为1的数的个数。
3. 类欧几里得算法：
   • 函数f(a, b, c, n)计算 ∑_{i=0}^n floor((a*i + b)/c)。
   • 利用该函数计算 ∑_{i=0}^n (x+i*z)/2^i 的整数部分，进而推导第i位的异或结果。
4. 异或结果计算：对于每一位i，若该位为1的数的个数为奇数，则结果的第i位为1。

###标程

#include<iostream>
#include<stdio.h>
using namespace std;
typedef long long ll;
const int maxn = 100;
ll x, y, z;
ll ans[maxn];

// 类欧几里得算法：计算∑_{i=0}^n floor((a*i + b)/c)
ll f(ll a, ll b, ll c, ll n) {
    if (!a) return b / c * (n + 1);  // 当a=0时，直接计算
    if (a >= c || b >= c)
        // 分解为更小规模的问题
        return f(a % c, b % c, c, n) + n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c);
    ll m = (a * n + b) / c;
    // 递归转换问题
    return n * m - f(c, c - b - 1, a, m - 1);
}

int main() {
    while (scanf("%lld%lld%lld", &x, &y, &z) != EOF) {
        ll res = 0;
        for (int i = 34; i >= 0; i--) {
            ll n = (y - x) / z;  // 项数
            // 计算∑_{i=0}^n floor((z*i + x)/2^i)
            ans[i] = f(z, x, (1ll << i), n);
            // 第i位的异或结果为(ans[i] - 2*ans[i+1]) % 2
            res += ((ans[i] - 2 * ans[i + 1]) & 1) * (1ll << i);
        }
        printf("%lld\n", res);
    }
    return 0;
}

关键步骤说明

1. 类欧几里得算法 f(a, b, c, n)：

   • 计算 ∑_{i=0}^n floor((a*i + b)/c)，时间复杂度为O(log n)。
   • 通过递归分解和转换，处理 a ≥ c 或 b ≥ c 的情况，最终转化为更小的子问题。

2. 逐位统计：

   • ans[i] 存储 ∑_{i=0}^n floor((z*i + x)/2^i)，即数列中所有数右移i位后的整数部分之和。
   • ans[i] - 2*ans[i+1] 计算第i位的1的个数，若为奇数则结果的第i位为1。

3. 位运算优化：

   • 使用 (1ll << i) 生成第i位的掩码，避免溢出。
   • & 1 快速判断奇偶性，高效计算异或结果。

示例解析

以输入 2 173 11 为例：

1. 数列范围：首项 x=2，公差 z=11，末项 x+kz ≤ 173，计算得 k=15，数列包含16项。
2. 按位计算：
   • 对于第0位（最低位）：统计数列中末位为1的数的个数，通过 f 函数计算并判断奇偶性。
   • 同理处理其他位，最终组合各位结果得到异或值。
3. 结果：数列 2, 13, 24, ..., 167 的异或和为48。

复杂度分析

• 时间复杂度：O(T * 35 * log n)，其中T为测试用例数，35为处理的位数，log n为类欧几里得算法的复杂度。
• 空间复杂度：O(1)，仅需常数额外空间。

正确性证明

1. 按位独立性：异或运算的每一位独立，逐位计算正确性成立。
2. 类欧几里得算法：函数 f 正确计算 ∑_{i=0}^n floor((a*i + b)/c)，通过数学归纳和递归转换保证正确性。
3. 奇偶性判断：ans[i] - 2*ans[i+1] 准确统计第i位1的个数，奇偶性决定异或结果。