Самый быстрый способ определения НОД всех элементов множества

Для решения задачи необходимо найти НОД множества. Может кто-либо предоставить код, или алгоритм, чтобы сделать это достаточно быстро.
Дополнительный вопрос: изначальная задача - найти числа, при деление на которые все элементы множества дают одинаковый остаток. Можно ли найти такие числа быстрее, чем перебором чисел от 2 до НОД всех элементов множества разностей изначального множества?

Ответ

1 - НОД - наибольший общий делитель.
Алгоритм для поиска НОД 2 чисел известен, но приведу его ещё раз.
long long gcd(long long a,long long b){ while (a && b) if (a > b) a%=b; else b%=a; return a+b; }
Тут используется допущение, что НОД(0,0)=0, это часто удобно.
Теперь, чтобы найти НОД нескольких чисел, нужно последовательно брать НОД от них.
long long gcd(const vector& 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 найти числа, при деление на которые все элементы множества дают одинаковый остаток.
Есть разные варианты, как это сделать. НО идея у вас перебирать от 2 до НОД неправильная. Пример: 5 и 9 дают остаток 1 при делении на 4. Но НОД(5,9)=1.
Если в наборе более 1 числа (предполагаю что все числа различны) то количество таких делителей будет не больше чем минимальное из этих чисел. Но это долго.
Пусть x = a*p + r, y = b*p + r Тогда x-y = (b-a)*p И значит делится на p аналогично для остальных пар. Поэтому ответ - все делители от НОД разностей всех чисел (Их N^2, но все необязательны, достаточно между соседними или от 1 ко всем, всего N-1 штука).
Доказательство. Пусть G = gcd(delt)
Тогда если x ≡ r (mod G). y = x + (y - x) => y = x + G*q => y ≡ r + G*q (mod G) => y ≡ r (mod G). Что и требовалось.
В обратную: для любых (x,y) x ≡ r (mod Q) y ≡ r (mod Q) G not | Q => x-y ≡ 0 (mod Q) => x-y делится на Q. Отсюда противоречие с тем что G - gcd();
Реализацию сами допишите.
Сложность - память O(n) или O(1) время O(n * log2(M) + sqrt(M) ). где M - максимальное значение. sqrt(M) - факторизация ответа, можно и без неё алгоритмы найти легко.