Tanmoy1228's blog

Solution Needed For Number Theory Problem
By Tanmoy1228, history, 9 years ago, In English

Problem: A simple task

can anyone give me any idea to solve the problem

with the mathematical proof

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

If a[i]%k = a[j]%k, then abs(a[j] — a[i])%k = 0. Therefore, any number that divides the absolute difference of all pairs of numbers will work. Therefore, find the GCD of the absolute differences between all pairs, and any divisors of that number will work. Note that this solution is O(n^2), which is fine for those bounds, but you can speed it up by considering only differences between consecutive elements of the array.

→ Reply