MZL's xor

MZL loves xor very much.Now he gets an array A.The length of A is n.He wants to know the xor of all (Ai+Aj)(1≤i,j≤n)
The xor of an array B is defined as B1 xor B2...xor Bn

Multiple test cases, the first line contains an integer T(no more than 20), indicating the number of cases.
Each test case contains four integers:n,m,z,l
A1=0,Ai=(Ai−1∗m+z) mod l
1≤m,z,l≤5∗105,n=5∗105

For every test.print the answer.

2
3 5 5 7
6 8 8 9

14
16

题意：

Ai=(Ai−1∗m+z)modl ，A1=0。求出所有任意两个Ai or Aj。1<=i,j<=n。

题解：

当i!=j时，必有两组Ai,Aj,Aj,Ai。他们的和相同，xor得0。0异或任何数为任何数本身。所以所有i!=j都不需要考虑只需求出当i==j时的结果。需要注意的是求出的Ai int可能会放不下。故开Long long 数组。

参考代码：

#include<stdio.h>
#define M 1000001
long long a[M];
int main()
{
	long long  t,n,m,z,l,sum;
	scanf("%lld",&t);
	while(t--)
	{
	    sum=0;
		scanf("%lld%lld%lld%lld",&n,&m,&z,&l);
        a[1]=0;
        for(int i=2;i<=n;i++)
        	a[i]=(a[i-1]*m+z)%l;
        for(int i=2;i<=n;i++)
            sum^=2*a[i];
        printf("%lld\n",sum);
	}
}