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

#cpp #алгоритм #математика

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

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

Ответы

Ответ 1

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 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) - факторизация ответа, можно и без неё алгоритмы найти легко.


Ответ 2

НОД можно найти по алгоритму Эвклида. Он прекрасно работает для более чем 2ух чисел.