Задача

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [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

Код программы

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");
		}
	}
}

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

Задача

Даны целые числа [latex]p[/latex] и [latex]q[/latex]. Получить все делители числа [latex]q[/latex], взаимно простые с числом [latex]p[/latex].

Тесты

q	p	Все делители числа q, взаимно простые с числом p
40	15	1 2 4 8
87	3	1 29

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static long gcd(long x, long y){
		return (y != 0) ? gcd(y, x%y) : x;
	}
	public static void main (String[] args) 
	{
		int q = 0, p;
		Scanner in = new Scanner(System.in);
		q = in.nextInt();
		p = in.nextInt();
		for (int i = 1; i <= q; i++)
		{ 
        	if((q % i) == 0) {
            	if (gcd(i,p) == 1)
                	System.out.println(i + " ");
        	}
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

public static long gcd(long x, long y){

return (y != 0) ? gcd(y, x%y) : x;

}

public static void main (String[] args)

{

int q = 0, p;

Scanner in = new Scanner(System.in);

q = in.nextInt();

p = in.nextInt();

for (int i = 1; i <= q; i++)

{

if((q % i) == 0) {

if (gcd(i,p) == 1)

System.out.println(i + " ");

}

Решение

Воспользуемся рекурсивной реализацией алгоритма Евклида. Пусть m и n — не равные нулю целые неотрицательные числа, и пусть [latex]m\geq n[/latex]. Тогда, если [latex]n=0[/latex], [latex]GCD(n,m)=m[/latex], а если [latex]n\neq 0[/latex], то для чисел [latex]m,n[/latex] и [latex]k[/latex], где [latex]k[/latex], где [latex]k[/latex] — остаток от деления [latex]m[/latex] и [latex]n[/latex], выполняется равенство [latex]GCD(m,n)=GCD(n,k)[/latex].

Для нахождения делителей числа [latex]q[/latex] взаимно простых с [latex]p[/latex], программа проверяет остатки от деления [latex]q[/latex] на все числа [latex]i[/latex] от [latex]1[/latex] до [latex]q[/latex]. Если остаток равен нулю, то число [latex]i[/latex] является делителем [latex]q[/latex]. Для каждого такого числа выполняется поиск наибольшего общего делителя (НОД — Greatest common divisor, GCD) [latex]i[/latex] и [latex]p[/latex] по алгоритму Евклида. [latex]1[/latex], то числа [latex]i[/latex] и [latex]p[/latex] взаимно простые.

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Tag Archives: взаимно простые числа

e-olymp 1154. Кружок хорового пения