poj3495 Bitwise XOR of Arithmetic Progression

因为异或运算看成可以每一位单独单独做加法运算，也就是求

$$\sum_{i=0}^{31}2^i\left(\sum_{j=0}^{\lfloor\frac {(y-x)}z\rfloor} \lfloor\frac{zj+x}{2^i}\rfloor)\%2\right)$$
不妨写成更一般的形式，求
$$\sum_{x=0}^{n-1}\lfloor\frac{ax+b}c\rfloor$$
首先把 $a$和 $b$整除的部分提出来，得到
$$\lfloor\frac ac \rfloor\frac{n(n-1)}2+\lfloor\frac bc\rfloor n+\sum_{x=0}^{n-1}\lfloor\frac{a\% c*x+b\%c}c\rfloor$$
对于后面这个东西，不妨记 $f(x)=\frac{a\% c*x+b\%c}c$。以点 $(n,\lfloor f(n)\rfloor)$为原点， $y$轴负方向为 $x$轴正方向， $x$轴负方向为 $y$轴正方向建立新的直角坐标系。考虑到 $y\ge f(n)$和 $x\lt 0$的区域都没有整点，可以把这个东西看成新坐标系下原直线的整点个数。因此需要表示出新坐标系下原直线的斜率、截距和定义域。
斜率就是 $\frac{c}{a\%c}$。定义域就是 $\lfloor f(n)\rfloor$。截距需要求出 $f(w)=\lfloor f(n)\rfloor$的 $w$，解方程得到 $w=n-n\%c-\frac{b\%c}{a\%c}$，因此截距是 $\frac{(an+b)%c}{a\%c}$。
于是我们惊喜地发现，斜率和截距的分母一样，因此变成了和原来问题形式相同的问题。而且原来的整数对 $(a,c)$变成了 $(c,a\%c)$。根据辗转相除，这样肯定能算完。于是问题就解决了，复杂度是 $O(\log ^2 n)$。

#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL solve(LL n,LL a,LL b,LL c)
{if (c==0) return 0;return a/c*n*(n-1)/2+b/c*n+solve((a%c*n+b%c)/c,c,(a*n+b)%c,a%c)&1;
}
int main()
{LL x,y,z,n,ans;while (scanf("%lld%lld%lld",&x,&y,&z)==3){ans=0;n=(y-x)/z;for (int i=0;i<32;i++) ans|=solve(n+1,z,x,1LL<<i)<<i;printf("%lld\n",ans);}
}