Проверьте, является ли целое число GCD некоторых элементов в заданном наборе

Question

Учитывая набор целых положительных чисел и целое число k. Все элементы в комплекте делится на k.

Как проверить, является ли k наибольшим общим делителем элементов в наборе?

Моя идея: Для каждого элемента a[i] в комплекте я делю его на k. Затем я получаю GCD всего элемента в наборе (который был изменен после того, как я разделил). Если GCD равен 1, то k является GCD некоторых элементов в наборе.

У меня есть несколько тестовых примеров, и я вижу это правильно. Но онлайн-судья не принимает. Пожалуйста, дайте мне представление или проверьте мой алгоритм и исправьте его. Большое спасибо.

Позвольте мне говорить яснее:

Например, = {10, 15, 18}:

k = 5 является НОД (10, 15). Ответ true

k = 3 - GCD (15, 18). Ответ true

k = 1 - GCD (10, 15, 18). Ответ true

k = 6 не является GCD любой группы, которая содержит более 2 целых чисел. Ответ false

Размер набора: < = 100000

EDIT: Извините за то, что неправильный пример. Это была моя ошибка. k = 3 не является GCD (10, 18). Но я подумал, что вы, возможно, знаете, что это 15, а не справа. :) Спасибо за ваши ответы, комментарии и вклад. Я проголосовал за принятый ответ ниже.

Answer 1

1 вопрос не некогерентно с примером:

в течение 10, 15, 18:

• 3 не является делителем 10, ни 6
• есть нет общего делителя

2 Ваш Вопрос может быть уменьшен так:

• к делят каждые элементы, поэтому разделить их => новых «уменьшенный» установить
• если к был НОД некоторого подмножества, то соответствующее приведенное подмножество имеет 1 как НОД (они являются простыми вместе)
• так что мы можем забыть к

3 проблема теперь: данный набор, это подмножество элементов простых вместе (или с 1, как НОД)?

, но если это верно из подмножества, это верно для всех элементов.

Так ваш алгоритм хорошо: принять A1, A2, и НОД, то НОД это А3, ...

Если в какой-то момент вы получаете 1, она закончена.

Answer 2

int gcd(int a, int b) { 
    int c; 
    while(a != 0) { 
    c = a; 
    a = b%a; 
    b = c; 
    } 
    return b; 
} 

bool function(int[] a, int n, int k) { 
    int numberOfGCD = 0; 
    for(int i = 0; i < n; i++) 
     for(int j = i+1; j < n; j++) 
      if(gcd(a[i], a[j]) == k) numberOfGCD++; 
    return numberOfGCD > 1; 
}