Простые числа и разложение на множители

ID 65959. 65959

На уроке информатики Фоме задали задачу о проверке гипотезы Гольдбаха.
Условие задачи выглядело так:
Гипотеза Гольдбаха (не доказанная до сих пор) утверждает, что любое четное число (кроме 2) можно представить в виде суммы двух простых чисел.
Фома легко решил данную задачу методом поиска "первого решения".
Дома, Фома заметил, что во время отладки, он получал решения, в которых одно из чисел было не очень большим.
Так, для числа 1000000, он получил разложение 1000000=17+999983. Фома решил проверить, в чем сложность гипотезы Гольдбаха.
Для этого Фома придумал задачу:
Определим функцию g(n) = количеству разложений числа n в сумму двух простых чисел. (разложения, отличающиеся порядком слагаемых, считаются одинаковыми).
На отрезке натуральных чисел от A до B найдите чётное число x такое, что: g(x) кратно 5 и имеет минимальное значение среди всех g(x) кратных 5 на этом отрезке.
Решите задачу Фомы.

Входные данные
Границы отрезка A, B (два натуральных числа 5≤ A<B≤106 )
Выходные данные
- "Impossible" если для всех чётных x из отрезка [A;B] значение g(x) не кратно 5.
- два числа - x, g( x ) ( g(x) кратно 5 и минимальное для A≤ x≤B). Если таких x несколько, то выведите минимальное значение x.

Примеры

ID 60169. Разность квадратов

На доске были выписаны два квадрата натуральных чисел: \(x^2\) и \(y^2\), где \(l \le y^2 < x^2 \le r\). Числа \(x^2\) и \(y^2\) стерли и выписали на доске их разность \(d\).

По заданным \(l\), \(r\) и \(d\) выясните, сколько различных пар натуральных чисел \(x^2, y^2\) могло быть выписано на доске.

Формат выходных данных
В первой строке даны три числа \(d\), \(l\) и \(r\) (\(1 \le d \le 10^9, 1 \le l \le r \le 10^{18}\)).

Формат входных данных
Выведите количество подходящих пар квадратов.

Примечание
В первом примере подходят числа 100 и 36. Во втором примере также подходят числа 256 и 196.

ID 56653. Призы победителям сборов

Оргкомитет и жюри Московской олимпиады проводят очередные учебно-тренировочные сборы. Победители туров на сборах получают в качестве приза мороженое. Поскольку мороженое имеет тенденцию таять, то оно должно храниться в холодильнике. Холодильник, имеющийся в 179 школе слишком мал для хранения всего запаса мороженого. Поэтому организаторы решили заказать специальный супер-пупер-большой холодильник. Новый холодильник должен быть параллелепипедом A × B × C и хранить ровно N кубических баночек мороженого размером 1 × 1 × 1. Для уменьшения потерь холода, общая площадь поверхности холодильника должна быть как можно меньше.

Например, если размер холодильника должен быть 12, возможными вариантами являются:

 
 

ID 56021. Заполните массив

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

Входные данные
Вводится одно натуральное число N (1≤N≤1000).

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

ID 55500. Простое число

По введенному натуральному числу K, не превосходящему 1 000 000, выдать K-ое по счету простое число.

Входные данные
Во входном файле находится одно натуральное число K.

Выходные данные
В выходной файл выведите K-е простое число.

ID 55406. Заполните массив

Требуется заполнить N элементов массива, пронумерованных числами от 1 до N (A[1]…A[N]), натуральными числами от 2 до N+1, использовав каждое число ровно один раз, так, чтобы значение каждого элемента массива делилось бы нацело на его номер (т.е. для каждого i A[i] делилось бы на i).

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

Входные данные
Вводится одно натуральное число N (1≤N≤60000).

Выходные данные
Выведите одно число — искомое количество способов заполнения массива.

Примечание
Массив можно заполнить единственным способом: 3 2
 

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

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

Входные данные
В первой строке находится единственное число N. 2 <= N <= 2³¹ - 1.

Выходные данные
Выводится список чисел в порядке неубывания, разделённых знаком "*".

ID 55095. Простые числа(2)

Вывести все простые числа от M до N включительно.

Входные данные
В первой строке находятся разделённые пробелом M и N. 2 <= M <= N <= 1 000 000.

Выходные данные
Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

ID 55088. Простые числа

Вывести все простые числа от M до N включительно.

Входные данные
В первой строке находятся разделённые пробелом M и N. 2 <= M <= N <= 300 000.

Выходные данные
Вывести числа в порядке возрастания, по одному в строке. Если между M и N включительно нет простых - вывести "Absent".

ID 55076. Дом оригинальности и гармонии

Строительная компания хочет построить дом, в котором будет n квадратных комнат. Каждая комната характеризуется своим размером — длиной стены. Обозначим размеры комнат в новом доме как a₁, a₂, …, a_n.

При этом для того, чтобы квартиры в доме активнее распродавались, компания объявила его «Домом оригинальности и гармонии». Оригинальность означает, что размер любой комнаты не должен делиться на размер никакой другой комнаты. Свойство гармонии требует, чтобы площадь любой комнаты делилась на размер каждой из комнат. Иначе говоря, для любых различных i и j должны выполняться условия: ai не делится на a_j, а a_i² делится на a_j.

Требуется по заданному числу n выбрать такие размеры комнат, чтобы выполнялись свойства оригинальности и гармонии. При этом с целью экономии строительных материалов размер каждой комнаты не должен превышать 2⁶³ – 1.

Входные данные
Строка содержит число n (1 ≤ n ≤ 1000).

Выходные данные
Выведите размеры комнат — n положительных целых чисел, не превосходящих 2⁶³ – 1. Разделяйте числа пробелами.

ID 55063. Марсианские факториалы

В 3141 году очередная экспедиция на Марс обнаружила в одной из пещер таинственные знаки. Они однозначно доказывали существование на Марсе разумных существ. Однако смысл этих таинственных знаков долгое время оставался неизвестным. Недавно один из ученых, профессор Очень-Умный, заметил один интересный факт: всего в надписях, составленных из этих знаков, встречается ровно K
 различных символов. Более того, все надписи заканчиваются на длинную последовательность одних и тех же символов.

Вывод, который сделал из своих наблюдений профессор, потряс всех ученых Земли. Он предположил, что эти надписи являются записями факториалов различных натуральных чисел в системе счисления с основанием K. А символы в конце - это конечно же нули - ведь, как известно, факториалы больших чисел заканчиваются большим количеством нулей. Например, в нашей десятичной системе счисления факториалы заканчиваются на нули, начиная с 5!=1·2·3·4·5 . А у числа 100! в конце следует 24 нуля в десятичной системе счисления и 48 нулей в системе счисления с основанием 6 - так что у предположения профессора есть разумные основания!

Теперь ученым срочно нужна программа, которая по заданным числам N и K найдет количество нулей в конце записи в системе счисления с основанием K числа N!=1·2·3·...·(N-1)·N, чтобы они могли проверить свою гипотезу. Вам придется написать им такую программу!

Входные данные
В первой строке входных данных содержатся числа N и K, разделенные пробелом, (1 <= N <= 10⁹, 2 <= K <= 1000).

Выходные данные
Выведите число X - количество нулей в конце записи числа N! в системе счисления с основанием K.

ID 54652. Перестановки

Ваня и Петя играют в следующую игру. Ваня пишет на бумаге какую-либо перестановку чисел от 1 до N (то есть выписывает все числа от 1 до N в некотором порядке) и расставляет на столе в ряд N предметов. После этого Петя переставляет предметы в соответствии с Ваниной перестановкой. А именно, Петя выполняет следующие действия: если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте, на место с номером a_i.

Обозначим предметы числами от 1 до N. Тогда начальное расположение предметов можно обозначить последовательностью чисел (1, 2, ..., N). К примеру, если N = 5, то начальное расположение предметов есть (1, 2, 3, 4, 5). Пусть Ваня написал перестановку <2, 5, 4, 3, 1>. Это значит, что после перемещения предметов они окажутся расставлены в следующем порядке: (5, 1, 4, 3, 2).

Однако, переставив предметы, Петя не останавливается на достигнутом и вновь переставляет их в соответствии с Ваниной перестановкой. Снова, если i-ое число в Ваниной перестановке равно a_i, то Петя ставит предмет, который стоит на i-ом месте на место с номером a_i. Так, если в приведенном выше примере повторно применить перестановку, предметы окажутся расположены в следующем порядке: (2, 5, 3, 4, 1).

Таким образом, Петя переставляет предметы в соответствии с Ваниной перестановкой, пока их расположение не окажется таким же, как исходное. В нашем примере Пете потребуется сделать еще 4 действия, порядок предметов после каждого из них будет следующим: (1, 2, 4, 3, 5), (5, 1, 3, 4, 2), (2, 5, 4, 3, 1), (1, 2, 3, 4, 5). Всего Пете потребовалось применить перестановку 6 раз.

Добрый Ваня хочет, чтобы Пете пришлось выполнить как можно больше действий. Помогите ему выбрать соответствующую перестановку.

Входные данные
Вводится единственное целое число N - количество предметов (1 <= N <= 100).

Выходные данные
Выведите перестановку чисел от 1 до N такую, что количество действий, которое придется сделать Пете, максимально. Если таких перестановок несколько, можно вывести любую.

ID 54300. Дробь

Известно, что сложение и умножение являются ассоциативными операциями. Это значит, что значение выражений вида \(a_1+a_2+\ldots +a_n\) и \(a_1\cdot a_2 \cdot \ldots \cdot a_n\) не зависит от порядка выполнения в них действий и следовательно не меняется при произвольной расстановке в этих выражениях скобок.

В отличии от сложения и умножения, деление — операция не ассоциативная. Так, значение выражения вида \(a_1/a_2/\cdots /a_n\) может меняться при расстановке в нем скобок.

Рассмотрим выражение вида \[p_1 / p_2 / \cdots / p_n,\] где все \(p_i\) — простые числа (не обязательно различные). Найдите количество возможных значений, которые может принять указанное выражение после расстановки в нем скобок, а также количество целых чисел среди этих значений.

Например, выражение \(3/2/2\) после расстановки скобок может принять два значения: \(3/4 = (3 / 2) / 2\) и \(3 = 3 / (2 / 2)\).

Формат входных данных
Первая строка содержит число \(n\) (\(1 \le n \le 200\)). Следующая строка содержат \(n\) натуральных чисел — \(p_1, p_2, \dots, p_n\). Все числа \(p_i\) простые и не превосходят \(10^4\).

Формат выходных данных
На первой строке выведите количество возможных значений, которые может принять выражение \(p_1 / p_2 / \cdots / p_n\) при заданных \(p_i\) после расстановки в нем скобок. На второй строке выведите количество целых чисел среди этих значений.

ID 44036. Уравновесить подарки

У Деда Мороза есть N мешков с подарками. Каждый мешок имеет вес a1, a2, ..., aN. Для равномерной нагрузки на сани Деду Морозу необходимо, чтобы вес всех мешков был одинаковым. Чтобы этого добиться, Дед Мороз своим волшебным посохом может выполнить одну из следующих операций любое количество раз, возможно ноль раз.

• Дед Мороз может выбрать любой мешок и если его вес кратен двум, то уменьшить вес в два раза.
• Дед Мороз может выбрать любой мешок и если его кратен трем, то уменьшить вес в три раза.

На каждую операцию у Деда Мороза уходит 1 секунда.

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

Примеры

ID 38733. Количество делителей

Подсчитайте количество натуральных делителей числа x (включая 1 и само число x).

Входные данные
Вводится натуральное число x (x < 30000).

Выходные данные
Выведите единственное число - количество делителей числа x.
 

Примеры

ID 38732. Делители числа

Выведите все натуральные делители числа x в порядке возрастания (включая 1 и само число).

Входные данные
Вводится натуральное число x

Выходные данные
Выведите все делители числа x

 

Примеры

ID 38731. Минимальный делитель

Найдите самый маленький натуральный делитель числа x, отличный от 1 (2 <= x <= 30000).

Входные данные
Вводится натуральное число x.

Выходные данные
Выведите наименьший делитель числа x, отличный от 1.

Примеры

ID 38575. Псевдопростые числа

Пусть a₁ = 2, a₂ = 3, a_n = a_1·a₂·...·a_n-1 – 1 при n ≥ 3. Назовем числа ai псевдопростыми. Для заданного натурального числа X нужно ответить на вопрос: можно ли X однозначно представить в виде произведения псевдопростых чисел (представления, отличающиеся только порядком множителей, считаются одинаковыми), и, если можно — выдать разложение.<

Входные данные
Вводится одно натуральное число X, 1 < X ≤ 10⁹.

Выходные данные
Выведите псевдопростые числа, произведение которых равно X, в произвольном порядке. Если разложения не существует или оно не единственно, выдать 0.
 

Примеры

ID 38433. Степень

Для того чтобы проверить, как ее ученики умеют считать, Мария Ивановна каждый год задает им на дом одну и ту же задачу — для заданного натурального A найти минимальное натуральное N такое, что N в степени N (N, умноженное на себя N раз) делится на A. От года к году и от ученика к ученику меняется только число A.
Вы решили помочь будущим поколениям. Для этого вам необходимо написать программу, решающую эту задачу.
Формат входных данных
Во входном файле содержится единственное число A (1 ≤ A ≤ 1000000000 — на всякий случай; вдруг Мария Ивановна задаст большое число, чтобы кого-нибудь “завалить”).
Формат выходных данных
В выходной файл выведите единственное число N.
 

Примеры

ID 38356. Сломанный калькулятор

У калькулятора есть две ячейки памяти: содержимое первой из них всегда отображается на табло, вторая является буфером. В начальный момент времени на табло калькулятора отображается целое число X, а в буфере записано число 0. У калькулятора работают только две клавиши: «+» и «=». При нажатии на «+» число, которое в данный момент отображено на табло, копируется в буфер. При нажатии на «=» число из буфера прибавляется к числу, отображенному на табло и результат отображается на табло, число в буфере при этом не меняется.

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

Входные данные
Входной файл содержит два целых числа X и Y. Каждое из этих чисел по модулю не превышает 10⁹.

Выходные данные
В первую строку выходного файла выведите одно число — количество нажатий клавиш, которое потребуется для получения числа Y. Если из числа X получить число Y с помощью указанных операций невозможно, в выходной файл выведите одно число –1.

Примеры