题目链接：poj 3495：Bitwise XOR of Arithmetic Progression
让你求 x + z , x + 2 z , . . . , x + k z ( x + k z ≤ y ) \displaystyle x + z,x + 2z,...,x + kz(x + kz \leq y) x+z,x+2z,...,x+kz(x+kz≤y) 的异或和 转化式子： ⨁ k = 0 ⌊ y − x z ⌋ x + k ∗ z \displaystyle\bigoplus_{k = 0}^{\lfloor\frac{y - x}{z}\rfloor}x+k*z k=0⨁⌊zy−x⌋x+k∗z
按位考虑，计算异或和第 p p p 位是否为 1,等价于计算 ∑ k = 0 ⌊ y − x z ⌋ ( ⌊ x + k ∗ z 2 p ⌋ % 2 ) \displaystyle\sum_{k = 0}^{\lfloor\frac{y - x}{z}\rfloor}(\lfloor\frac{x+k*z}{2^p}\rfloor \% 2) k=0∑⌊zy−x⌋(⌊2px+k∗z⌋%2) = ∑ k = 0 ⌊ y − x z ⌋ ( ⌊ x + k ∗ z 2 p ⌋ − 2 ⌊ x + k ∗ z 2 p + 1 ⌋ ) =\displaystyle\sum_{k = 0}^{\lfloor\frac{y - x}{z}\rfloor}(\lfloor\frac{x+k*z}{2^p}\rfloor - 2\lfloor\frac{x+k*z}{2^{p + 1}}\rfloor) =k=0∑⌊zy−x⌋(⌊2px+k∗z⌋−2⌊2p+1x+k∗z⌋) 套类欧几里得模板求解即可。
代码：
#include<iostream> #include<stdio.h> using namespace std; typedef long long ll; const int maxn = 100; ll x,y,z; ll ans[maxn]; ll f(ll a,ll b,ll c,ll n) { if(!a) return b / c * (n + 1); 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,tmp; for(int i = 34; i >= 0; i--) { ll n = (y - x) / z; ans[i] = f(z,x,(1ll << i),n); res += ((ans[i] - 2 * ans[i + 1]) & 1) * (1ll << i); } printf("%lld\n",res); } return 0; }