Гордей на уроках информатики узнал, что шифровании методом RSA можно организовать с помощью тройки простых чисел.
Для экспериментов, Гордей решил упростить выбор троек простых чисел.
Гордей решил, что тройка простых чисел (a, b, c) будет
"m-подходящей", если:
- a > b > c
- записи чисел b, с в системе счисления по основанию m отличаются
от записи числа a в системе счисления по основанию m только в одном разряде
- число a назовем "ведущим числом тройки"
Примеры:
| a, b, c |
m |
пояснения |
| 43 41 11 |
2 |
43 = 1010112
41 = 1010012
11 = 10112
числа 41 и 11 простые и отличабтся от числа 43 только в одном разряде
(41 в разряде десятков, а 11 в разряле сотен тысяч)
Числа 35 и 42 меньше 43 и тоже имеют отличным от него один разряд
(в двоичной системе счисления), но они не простые |
| 79 73 61 |
3 |
79 = 22213
73 = 22013
61 = 20213
Троичная запись чисел 78, 76, 70, 52, 25 отличаются от троичной записи
числа 79 только в одном разряде, но они не простые |
| 73 71 59 |
7 |
73 = 1337
71 = 1317
59 = 1137
Остальные числа (337, 1237, 1037, 1327, 1307 ) отличающиеся от 73
в одном разряде есть четные числа, а значит составные
|
Гордей не очень хорошо программирует, поэтому просит помочь в решении следующей задачи:
- Задано простое число m не превосходящее 100
- Задан отрезок [X; Y] ( 0< X < Y <1_000_000)
- Найдите все "m-подходящие" тройки простых чисел, таких, что
Y <= c < b < a <= X
В качестве ответа определите:
- Количество различных различных "ведущих чисел троек"
- Значение, которое в качестве "ведущего числа" имеет максимальное количество троек
Примеры
| m, X, Y |
Ожидаемый
результат |
Пояснения |
| 2 10 50 |
2
43 |
Для отрезка [10; 50] найдется всего два "ведущих" числа "2-подходяших" троек:
43, 31
43 = 1010112; 41 = 1010012; 11= 10112;
31 = 111112; 29 = 111012; 23= 101112;
других троек нет, а 43 < 31 |
| 7 1 100 |
8
47 |
Для отрезка [1, 100] и системы счисления с основанием 100
ведущими числами могут быть
73 =1337(одна тройка 73-71-59)
47=657 (три тройки 47-43-19, 47-43-5, 47-19-5)
41=567 (одна тройка 41-37-13)
37=527 (одна тройка 37-23-2)
31=437 (три тройки 31-29-17, 31-29-3, 31-17-3)
19=257 (одна тройка 19-17-5)
13=167 (одна тройка 13-11-7)
5=57 (одна тройка 5-3-2)
47 будет в ответе, так как с "ведущим" 47 будет три тройки, а для 73 их только одна |
| 7 10 100 |
4
73 |
В ответе будет 73, поскольку у всех "ведущих" чисел (73, 47, 43, 31) будет по одной тройка |
| 2 12345 67890 |
1127
65357 |
|
| 97 12345 67890 |
5095
27823 |
|
Входные данные
1 строка m, A, B - (m - простое число не более 100, 9 < A < B< 1_000_000)
Выходные данные
1 строка - натуральное число - количество простых чисел из отрезка [X; Y],
которых могут быть "ведущим число" хотя бы одной "m-подходящей" тройки
2 строка - простое число из отрезка [X;Y], которое "начинает"( является "ведущим числом тройки") максимальное количество троек.
Если таких значений несколько, то выведите максимальное из них
Пояснения:
- Гарантируется, что на отрезке [X;Y] найдется хотя бы одна "m-подходящая" тройка простых чисел
- Не требуется считать количество"m-подходящих троек, для каждого "ведущего" числа, а требуется отределить для какого числа
оно будет максимально
,