#1281

Счастливые цифры

Темы: [Простые числа и разложение на множители] [Разные системы счисления]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Заключительный этап, 2008, 2 день, Задача A ]

Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ≥ 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.

Требуется написать программу, которая по заданным числам n и k найдет такое d, чтобы число n в системе счисления с основанием d заканчивалось как можно большим количеством цифр k.

Входные данные

Вводятся два целых десятичных числа n и k (1 ≤ n ≤ 10¹¹; 0 ≤ k ≤ 9).

Выходные данные

Выведите два числа: d — искомое основание системы счисления и l — количество цифр k, которым заканчивается запись числа n в этой системе счисления. Если искомых d несколько, выведите любое из них, не превосходящее 10¹² (такое всегда существует).

Примеры

		комментарий
49 1	3 2	49₁₀ = 1211₃
7 5	3 0	Ни в одной системе счисления 7 не заканчивается на цифру 5

Примеры

Входные данные

4 4

Выходные данные

5 1

Входные данные

9 9

Выходные данные

10 1

#1453

Полярные единички

Темы: [Простые числа и разложение на множители] [Остатки]

Программист на Северном полюсе работал за компьютером в варежках и поэтому мог набирать только 0 и 1, а клавиша 0 запала. Сможет ли он набрать число, состоящее только из единиц и при этом кратное заданному N?

Входные данные

Программе дано число N (1 ≤ N ≤ 10⁶).

Выходные данные

Вывести минимальное число, удволетворяющее требованию, или "NO" , если такого числа не существует.

Примеры

Входные данные

Выходные данные

NO

Входные данные

Выходные данные

111111111111111111

#1538

Факторизация числа

Темы: [Простые числа и разложение на множители]

Напишите программу, которая будет разлагать натуральное число \(n > 1\) на простые сомножители.

Входные данные

На вход программе подается натуральное \(n \le 2×10^9\).

Выходные данные

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

Примеры

Входные данные

Выходные данные

5=5

Входные данные

Выходные данные

12=2*2*3

#1639

Делители

Темы: [Простые числа и разложение на множители]

Источники: [ Личные олимпиады, Украинские олимпиады, 2006, Задача A ]

По заданному натуральному числу N необходимо вычислить количество натуральных чисел, которые есть делителями N! (факториала числа N).

Например, при N=4, N!=4·3·2·1=24. Это число имеет следующие делители: 1, 2, 3, 4, 6, 8, 12, 24. Таким образом, искомое количество составляет 8.

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

Формат входных данных

Единственная строка входного файла содержит одно целое число N (1≤N≤45).

Формат выходных данных

Единственная строка выходного файла должна содержать одно целое число –найденное количество делителей числа N!

Примеры

Входные данные

Выходные данные

#1660

Суперчисла

Темы: [Простые числа и разложение на множители]

Источники: [ Личные олимпиады, Всероссийская олимпиада школьников, Региональный этап, Кировская открытая областная олимпиада, 2004, Задача A ]

Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…\(B\)]. Требуется найти все суперчисла из заданного диапазона [\(A\)…\(B\)].

Входные данные

Во входном файле даны два числа \(A\) и \(B\) (2 ≤ \(A\) ≤ \(B\) ≤ 40000), определяющие диапазон [\(A\)…\(B\)].

Выходные данные

В выходной файл вывести все найденные суперчисла из заданного диапазона в возрастающем порядке.

Примеры

Входные данные

3 10

Выходные данные