POJ3495 Bitwise XOR of Arithmetic Progression

Bitwise XOR of Arithmetic Progression

Write a program that, given three positive integers x, y and z (x, y, z < 2³², x ≤ y), computes the bitwise exclusive disjunction (XOR) of the arithmetic progression x, x + z, x + 2z, …, x + kz, where k is the largest integer such that x + kz ≤ y.

题解

https://blog.csdn.net/PoPoQQQ/article/details/46853933

求异或和当然要逐位考虑。第 (i) 位的结果是：

[(sum_{i=0}^{lfloorfrac{y-x}{z} floor} lfloorfrac{x+iz}{2^i} floor)mod 2 ]

这个就是经典的类欧问题了。

[sum_{x=0}^N lfloorfrac{ax+b}{c} floor = Nlfloorfrac{aN+b}{c} floor-sum_{x=0}^{lfloorfrac{aN+b}{c} floor-1} lfloorfrac{cx+c-b-1}{a} floor ]

时间复杂度 (O(log^2 n))。

int64 calc(int64 a,int64 b,int64 c,int64 n){
	if(a==0 or (a*n+b)/c==0)
		return (a*n+b)/c*(n+1);
	if(a>=c)
		return a/c*n*(n+1)/2+calc(a%c,b,c,n);
	if(b>=c)
		return b/c*(n+1)+calc(a,b%c,c,n);
	return (a*n+b)/c*n-calc(c,c-b-1,a,(a*n+b)/c-1);
}
int main(){
	for(int64 x,y,z;scanf("%lld%lld%lld",&x,&y,&z)!=EOF;){
		int64 ans=0;
		for(int i=0;i<32;++i)
			ans|=(calc(z,x,1LL<<i,(y-x)/z)&1)<<i;
		printf("%lld
",ans);
	}
	return 0;
}