To solve the problem it is necessary to find the GCD of the set. Can someone provide the code, or algorithm, to do this quickly enough.

An additional question: the initial task is to find the numbers, with the division into which all the elements of the set give the same remainder. Is it possible to find such numbers faster than by enumerating numbers from 2 to NOD of all elements of the set of differences of the initial set?

    2 answers 2

    1 - GCD - the greatest common factor.

    The algorithm for searching GCD 2 numbers is known, but I will give it again.

    long long gcd(long long a,long long b){ while (a && b) if (a > b) a%=b; else b%=a; return a+b; }

    It uses the assumption that the НОД(0,0)=0 , it is often convenient.

    Now, in order to find the GCD of several numbers, you need to consistently take the GCD from them.

      long long gcd(const vector<long long>& num){ if (num.size() == 0) return 0; if (num.size() == 1) return num[0]; long long res = gcd(num[0],num[1]); for (auto i=2;i<num.size() && res!=1;i++) //&& res!=1 можно не писать res = gcd(res,num[i]); }

    find the numbers, the division into which all elements of the set give the same remainder.

    There are different options for how to do this. But the idea you have to go from 2 to the GCD is wrong. Example: 5 and 9 give the remainder 1 when divided by 4. But GCD (5.9) = 1.

    If there is more than 1 number in the set (I assume that all numbers are different ), then the number of such divisors will be no more than the minimum of these numbers. But it is a long time.

    Let x = a*p + r, y = b*p + r Then xy = (ba)*p And it means that it is divisible by p for the other pairs. Therefore, the answer is all the dividers from the GCD of the differences of all numbers (There are N ^ 2, but all are optional, it is enough between neighboring numbers or from 1 to all, the total is N-1).

    Evidence. Let G = gcd(delt) .

    Then if x ≡ r (mod G). y = x + (y - x) => y = x + G*q => y ≡ r + G*q (mod G) => y ≡ r (mod G). x ≡ r (mod G). y = x + (y - x) => y = x + G*q => y ≡ r + G*q (mod G) => y ≡ r (mod G). As required.

    Inverse: для любых (x,y) x ≡ r (mod Q) y ≡ r (mod Q) G not | Q => xy ≡ 0 (mod Q) => xy делится на Q. Отсюда противоречие с тем что G - gcd(); для любых (x,y) x ≡ r (mod Q) y ≡ r (mod Q) G not | Q => xy ≡ 0 (mod Q) => xy делится на Q. Отсюда противоречие с тем что G - gcd();

    Realization add yourself.

    Complexity - memory O(n) or O(1) time O(n * log2(M) + sqrt(M) ) . where M is the maximum value. sqrt(M) - factoring the answer, you can easily find algorithms without it.

    • Thank you so much for the detailed answer to both questions. But at the expense of my idea: I offered to sort through the numbers from 2 to the GCD of the differences of elements, but, apparently, did not write it clearly enough, which caused misunderstanding. And another question arose: can the difference be counted in a row and take it modulo, or is it worth first sorting the array to save time on subsequent calculations? - Ka_ktus 3:51 pm
    • @Ka_ktus there is no difference, I wrote you can at least from the maximum to all take as you like. You can slightly change the NOD algorithm so that it works with negative ones. - pavel

    GCD can be found using the Euclidean algorithm. It works great for more than 2 numbers.

    • You can implement the algorithm as follows: store the set on the heap (at the top there should be a maximum element of the set); create a while loop in which to apply the Euclidean algorithm: with a built-in function to find the minimum element, and subtract it from the maximum one in the heap, rebuild the heap. And so on until the elements in the heap become equal. You can find out when this happens like this: compare the minimum and the first element in the heap. - Zakoulov
    • one
      uh ... don't do that. A bunch of more use where it is not needed at all. - pavel