Блог пользователя Tanmoy1228

Автор Tanmoy1228, история, 8 лет назад, По-английски

Problem: A simple task

can anyone give me any idea to solve the problem

with the mathematical proof

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.