Today i was solving 424C - Magic Formulas on codeforces and found a interesting solution to it which uses difference array as said in the title. First, instead of trying to calculating a[i] xor (i mod 1) xor (i mod 2) xor (i mod 3) xor ..... xor (i mod n) for every i lets just combine part including mods and add a[i] to the answer (since xor have a property (a xor b) xor c = (a xor c) xor b). So after initializing an array a we have n*n random numbers from 0 to n-1 and we need to find xor of that numbers. How we can find that? xor have a property: a xor a = 0 a xor a xor a = a, so we need to just calculate frequency array and add i to the answer if cnt[i] is odd. Now lets calculate frequency array: for every number i list of 1 mod i, 2 mod i, ..... is periodic every i times. so lets add floor(n/i) to every element in cnt in range [0,i-1], and if n is not divisible by i add 1 to every cnt in range [1,n mod i], but this would be to slow if we iterate by every number, so we use difference array algorithm since we need cnt array only after all queries or since all queries are offline, if you don't know difference array algorithm you can learn it here. So let's say that x = floor(n/i) so we add x to cnt[0] and subtract x from cnt[i] and if n is not divivsible by i add 1 to cnt[1] and subtract 1 from (n mod i)+1. Then do cnt[i]+=cnt[i-1] for every i 1<=i<n and if cnt[i] is odd add i to the answer. code