Задача №112777. Счастливые цифры
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами k. Поэтому каждый раз, когда он видит какое-нибудь натуральное число n, он сразу пытается подобрать такое d (d ≥ 2), что число n в системе счисления с основанием d заканчивается как можно большим количеством цифр k.
Требуется написать программу, которая по заданным числам n и k найдет такое d, чтобы число n в системе счисления с основанием d заканчивалось как можно большим количеством цифр k.
Вводятся два целых десятичных числа n и k (1 ≤ n ≤ 1011; 0 ≤ k ≤ 9).
Выведите два числа: d — искомое основание системы счисления и l — количество цифр k, которым заканчивается запись числа n в этой системе счисления. Если искомых d несколько, выведите любое из них, не превосходящее 1012 (такое всегда существует).
Примеры
|
|
| комментарий |
| 49 1 | 3 2 | 4910 = 12113 |
| 7 5 | 3 0 | Ни в одной системе счисления 7 не заканчивается на цифру 5 |
Система оценивания
Группа 0. Тесты из условия, оцениваются в 0 баллов.Группа 1. N <= 1000, оценивается в 30 баллов, баллы начисляются при прохождении всех тестов группы.
Группа 2. N <= 1000000000, оценивается в 40 баллов, баллы начисляются при прохождении всех тестов группы.
Группа 3. Полные ограничения, оценивается в 30 баллов, баллы начисляются при прохождении всех тестов группы.