Базовая задача «Решето Эратосфена»

НОД и НОК.

Разложение на простые множители.

 

Базовая задача «НОД и НОК n чисел»

Добрейшей души учительница математики Марья Ивановна решила порадовать своих учеников домашним заданием по программе 5 класса. Каждый ученик получил список их N (2<=N<=100) натуральных чисел, найти НОД и НОК которых ему предстоит к завтрашнему утру. Поскольку у всех разные варианты, то ребята обращаются к Вам за помощью. Напишите программу, которая быстро позволит им посчитать НОД и НОК данного набора чисел.

Обязательное требование: использовать пользовательскую (-ие) процедуру (-ы) или (и) функцию (-и).

 

Тесты к базовой задаче:

 

№ п/п	Ввод	Вывод
	46 18 92 34 66	NOD=2 NOK=154 836
	78498 17 31 3100 100 2	NOD=1 NOK=2 068 422 300

 

Базовая задача «Решето Эратосфена»

(Время: 1 сек)

Найти количество простых чисел от 1 до N (N<=900 000).

Дружные числа acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 25%)

Будем называть два числа дружными, если они состоят из одних и тех же цифр. Например, числа 1132 и 32321 являются дружными, а 12 и 123 – нет (в первом числе нет цифры 3). Требуется написать программу, которая определит, являются ли два заданных числа дружными.

Входные данные: Входной текстовый файл INPUT.TXT содержит в первой строке натуральное число K – количество тестов. Количество тестов не превышает 10. В следующих K строках содержатся по два целых числа A и B, разделенные одним пробелом (0 < A < 10⁹, 0 < B < 10⁹).

Выходные данные: Выходной текстовый файл OUTPUT.TXT должен содержать K строк. Для каждого теста в отдельной строке надо выдать сообщение “YES”, если A и B являются дружными, или “NO”, если не являются. В сообщениях кавычки не печатать.

№	input.txt	output.txt
	1 1132 32321	YES

 

№	input.txt	output.txt
	2 12 123 11 111	NO YES

 

Наилучший делитель acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 26%)

Будем говорить, что число a лучше числа b, если сумма цифр a больше суммы цифр числа b, а в случае равенства сумм их цифр, если число a меньше числа b. Например, число 124 лучше числа 123, так как у первого из них сумма цифр равна семи, а у второго – шести. Также, число 3 лучше числа 111, так как у них равны суммы цифр, но первое из них меньше.

Дано число n. Найдите такой его делитель (само число n и единица считаются делителями числа n), который лучше любого другого делителя числа n.

Входные данные: Первая строка входного файла содержит целое число n (1 ≤n≤10⁵).

Выходные данные: В выходной файл выведите ответ на задачу.

№	input.txt	output.txt

Красивые числа - 2 acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 26%)

Будем называть число красивым, если сумма его цифр в десятичной системе счисления делится на количество цифр в нем (в десятичной системе счисления).

Необходимо найти N-ое в порядке возрастания красивое число.

Входные данные: Входной файл input.txt содержит целое число N. (1 <=N<=100 000)

Выходные данные: В выходной файл OUTPUT.TXT выведите ответ на задачу.

№	input.txt	output.txt

Разложение на простые множители acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 27%)

Требуется вывести представление целого числа N в виде произведения простых чисел.

Входные данные: Входной файл input.txt содержит натуральное число N (2 ≤N≤ 2³¹-1).

Выходные данные: В выходной файл OUTPUT.TXT выведите список простых множителей числа N в порядке неубывания, разделенных знаком «*».

№	input.txt	output.txt
		2*3*5

Гадание - 2 acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 28%)

Маша недавно прочитала в книге «Теория чисел и предсказание будущего» о новом способе гадания. Способ заключается в следующем: надо выбрать целое положительное число N и посчитать количество чисел, меньших N и взаимно простых с ним. Это количество и будет результатом гадания.

Поскольку гадать приходится достаточно часто, а процесс гадания достаточно трудоемок, Маша попросила вас написать программу, считающую результат гадания.

Два числа называются взаимно простыми, если их наибольший общий делитель равен 1. Наибольшим общим делителем двух чисел a и b называется наибольшее целое положительное число, на которое делятся и a, и b.

№	input.txt	output.txt

Входные данные: Входной файл INPUT.TXT содержит целое положительное число N (1 ≤ N ≤ 10⁵).

Выходные данные: В выходной файл OUTPUT.TXT выведите одно число – результат гадания.

Апельсины acmp.ru

(Время: 1 сек. Память: 16 Мб Сложность: 31%)

Катя решила пригласить к себе в гости n друзей. Так как ее друзья очень любят фрукты, то в качестве угощения для них она купила m одинаковых апельсинов.

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

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

Входные данные: Входной файл INPUT.TXT содержит два положительных целых числа n и m (1 <= n, m <= 10⁹).

Выходные данные: В выходной файл OUTPUT.TXT выведите ответ на задачу.

№	input.txt	output.txt
	2 5
	2 4