Поиск номеров с заданными значениями GCD

Question

Я искал алгоритм Евклида для поиска GCD чисел. Теперь его можно использовать для поиска GCD двух заданных чисел. Однако, если мне присваивается GCD одного числа с несколькими другими числами, например, GCD первого номера с тремя другими номерами (включая себя), то есть

Дано: GCD of a, GCD a с b, GCD группы a с c, GCD группы a с d. , и то же самое относится к другим номерам, то есть GCD из b с a, b с b, .....

Затем, как я могу найти отдельные номера? Я знаю, что GCD (a, a) = a, но проблема здесь заключается в том, что отдельные данные GCD находятся в произвольном порядке, и поэтому я не знаю, какое входное число является GCD, из которых два числа. В этом случае, как мне найти отдельные номера?

Вот мой НОД код:

int gcd(int a,int b) 
{ 
    if(b==0) 
    { 
     return a; 
    } 
    return gcd(b,a%b); 
} 

Пример: Допустим, вход дал есть,

3 1 3 1 4 2 2 3 6 
3 //(total numbers we have to find in original array) 

Тогда выход должен быть, 3 4 6. Потому что, если вычислить НОД парно (всего 9 пар и, следовательно, 9 чисел в качестве входных данных) каждого из этих чисел, то мы получаем результат, как указано выше.

Explanation: 3 -> GCD of (3,3) 
1 -> GCD of (3,4) 
3 -> GCD of (3,6) 
1 -> GCD of (4,3) 
4 -> GCD of (4,4) 
2 -> GCD of (4,6) 
6 -> GCD of (6,6) 
3 -> GCD of (6,3) 
2 -> GCD of (6,4) 

Поэтому я должен найти номера, GCD которых указан в качестве входных данных. Следовательно, (3,4,6) - эти числа.

Answer 1

Я думаю, что вы можете сделать это с помощью следующего процесса:

1. Найти и удалить большое количество, это один из первых номеров
2. Compute НОД числа только что на шаге 1, с все числа, ранее обнаруженные на шаге 1.
3. Удалить каждый из этих вычисленных ГКД из входного массива ГКД (строго говоря удалить 2 копии каждого GCD)
4. Повторить, пока все числа не будут найдены

Дело в том, что это происходит не так, если наибольшее число x, найденное на шаге 1, не является одним из исходных чисел. Однако это может произойти только в том случае, если x является gcd двух других чисел. Эти другие числа должны быть как минимум равны x, но все такие gcds были удалены на шаге 3. Поэтому x всегда является одним из исходных чисел.

Answer 2

Если вторая строка входного файла является 1, то первая строка входных данных будет иметь только один номер, и благодаря вашему наблюдению, что gcd(a, a) = a, значение a будет то, что значение находится на первую строке ввода ,

Если значение на второй строке ввода больше 1, то проблему можно уменьшить, используя следующее наблюдение. Учитывая положительные целые числа a и b, мы знаем, что gcd(a, b) <= a = gcd(a, a) и gcd(a, b) <= b = gcd(b, b) всегда будут иметь место. Поэтому мы можем заключить, что наибольшие два числа в первой строке ввода должны быть частью основного набора чисел. Самые большие два числа могут быть равны, но в вашем примере они равны 4 и 6, и они не равны.

Если найдется более двух цифр, назовем самые большие два a и b. Поскольку теперь мы знаем значение a и b, мы можем вычислить gcd(a, b) и удалить два вхождения этого значения из рассмотрения в качестве одного из входных чисел. Мы удаляем два вхождения, потому что gcd(a, b) = gcd(b, a) находятся в списке номеров ввода. Затем, используя аналогичную логику, мы заключаем, что наибольшее число, оставшееся после a, b, gcd(a, b) и gcd(b, a), должно быть одним из номеров ввода.

Промыть, полоскать, повторить.

Answer 3

Это на самом деле довольно легко:

• сосчитать, сколько раз в массиве появляется каждый отдельный номер
• если граф является нечетным, то это одна из чисел в наборе
• если что число равно, это не один из чисел в вашем наборе.

сделано.

Это работает, потому что когда x! = Y, gcd (x, y) = gcd (y, x) и это число будет в массиве дважды. Только значения, которые поступают из gcd (x, x), будут в массиве один раз, что приведет к нечетному числу этого конкретного значения.