xor满足交换律,问题可以转化为如何快速求(1 mod i)xor(2 mod i)xor(3 mod i)...(n mod i),结果是1xor2xor3...xor i xor1xor2xor3......
相同的可以抵消,要用到前缀和。code:
var n,i,x,ans:longint; an,sum:array[0..1000000] of longint; begin readln(n); for i:=1 to n do begin read(x); ans:=ans xor x; end; for i:=1 to n do sum[i]:=sum[i-1] xor i; for i:=1 to n do begin if n mod i=0 then begin if (n div i) mod 2=1 then an[i]:=sum[i-1] else an[i]:=0; continue; end; if (n div i) mod 2=1 then begin an[i]:=sum[i-1] xor sum[n mod i]; end else begin an[i]:=sum[n mod i]; end; end; for i:=1 to n do ans:=ans xor an[i]; write(ans); end.