Задача
В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex]-й для распевки поёт гамму.
Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.
Входные данные
Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex]. ([latex]1 ≤ N, M ≤ 103[/latex]).
Выходные данные
Для каждого тестового случая в отдельной строке выведите «YES», если в разминке примут участие все участники хора, в противном случае выведите «NO».
Тесты
| Входные данные | Выходные данные |
|---|---|
| 1000 1000 1 1 |
NO YES |
| 2 5 3 7 14 15 49 37 |
YES YES YES YES |
| 14 16 891 6 441 9 777 111 |
NO NO NO NO |
| 4 1 6 3 |
YES NO |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
import java.util.Scanner; public class Main { public static int gcd(int p, int q) { if (q == 0) return p; else return gcd(q, p % q); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String a; while(sc.hasNextInt()){ int p = sc.nextInt(); int q = sc.nextInt(); a = gcd(p, q)==1? "YES":"NO"; System.out.print(a + "\n"); } } } |
Решение
Пусть у нас есть [latex]N[/latex] певцов. Пронумеруем их по порядку от [latex]0[/latex] до [latex]N — 1[/latex]. Распевается каждый [latex]M[/latex]-й. И пусть НОД ([latex]M, N) = k \geq 2[/latex]. Тогда, например, [latex]k — 1[/latex]-ый певец никогда не распоется.
Ссылки
Условие задачи на сайте E-Olymp
код задачи на Ideone