Problem Link — https://codeforces.me/contest/2085/problem/E

Code — https://codeforces.me/contest/2085/submission/312319353

Approach and Proof-

For the moment, consider that B isn't shuffled. In that case, a[i]%k = b[i].

So b[i] is just the remainder when a[i] is divided by k. From factor Theorem we know, dividend = divisor × quotient + remainder.

Say the quotient is q. Then rewriting this using factor Theorem-

a[i] = k*q + b[i]

So a[i] — b[i] = k*q.

Now let's do it for all elements ie,

a[1] — b[1] = k*q1 a[2] — b[2] = k*q2 ...... a[n] — b[n] = k*qn

Adding them all, we get

Sum of all of A — sum of all of B = k*(q1+q2+...qn)

Now in the start we assumed an unshuffled B. But this holds true for even shuffled B because no matter what the order the sum remains the sum.

Observation from this- No matter what the order of B, the difference of sums of both A and B must be a multiple of k. So, we can only have such a k which a divisor of (sum of A — sum of B). Let's call that difference of sums d.

Now we can consider 3 cases-

1. If d = 0, then B must be a Permutation of A. Proof — notice that an element of B can never be greater than the corresponding element of A it got generated from because x%y must be less than x. So d = 0, every element of B must be equal to its generator. So B must be a permutation of A. So, we can always have max(A) + 1 as an answer because x%y for any x < y gives x.
2. If d = 1, all elements of b must be 0. This is because the only divisor of 1 is 1 itself so we only have k = 1 as a valid answer and any number % 1 = 0. So if there is any non zero element in B and is -1 else it is 1.
3. In every other case consider all the divisors of d as a valid answer and make a frequency map of a[i]%(divisor of d). If frequency map of b = this new freq map only then it's a valid k. This is literally brute force.

So what part of my proof is wrong which is causing the WA verdict?