Условие задачи:
В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.
Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex], где [latex]\left( 1 \le N, M \le {10}^{3} \right).[/latex]
Выходные данные
Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».
Тесты:
| n | m | answer |
| 4 | 1 | YES |
| 6 | 3 | NO |
Решение:
Для начала нам надо найти наибольший общий делитель(НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице то все ученики распоются и мы выводим «YES» в другом случае мы выводим «NO».
Код:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <iostream> using namespace std; int main() { int n, m, p; while(cin >> n >> m) { if (m > n) { p = n; n = m; m = p; } while (m > 0) { p = n % m; if (p != 0) { n = m; m = p; } else break; } cout<<(m==1?"YES": "NO")<<endl; } return 0; } |
Всё правильно. Зачтено.
Было бы очень хорошо, если бы Вы написали в своих пояснениях, что НОД равен 1 означает взаимно простые числа и объяснили почему в этом случае распоются все. Желательно со ссылками.
Кстати, первый условный оператор можно просто удалить, а второй внести в условие второго цикла. Сейчас это условие всегда выполняется. Получится что-то вроде