Счастливые цифры
시간 제한2초메모리 제한512 MB
자연수 n과 숫자 k가 주어질 때, n을 d진법으로 썼을 때 끝에 k가 최대한 많이 연속으로 오도록 하는 진법 d와 그 개수를 구한다.
문제
Школьнику Васе нравятся числа, которые заканчиваются счастливыми для него цифрами 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 (такое всегда существует).