Обучение опасности
Преподавание студентам — это увлекательное занятие, но иногда оно может привести к неожиданным ситуациям, как это произошло со мной недавно. Я вел курс CSE3021 (Математический анализ для компьютерных наук) в университете и на первом занятии объяснял некоторые базовые концепции. В частности, я учил студентов, как определять количество конечных нулей в n! (факториал n) в системе счисления с основанием b. Многие из вас знают, что кратность простого множителя p в n! можно вычислить с помощью формулы
+ ... до бесконечности.
Эта формула также может быть использована для определения количества конечных нулей в n!.
После объяснения формулы я продемонстрировал, как найти количество конечных нулей в 200! в десятичной системе счисления и с улыбкой предложил студентам определить количество конечных нулей в 100! в шестнадцатеричной (основание 16) системе счисления. Я знал, что правильный ответ — 24, и к моему удивлению, один из студентов дал правильный ответ всего через несколько минут. Я его поздравил, но вскоре обнаружил, что он на самом деле посчитал количество конечных нулей в 100! в десятичной системе, и случайно оба ответа (для шестнадцатеричной и десятичной систем) оказались 24. Это было немного неловко, и теперь мне нужна ваша помощь, чтобы выяснить, почему ответы совпали. Вам дано число n, и нужно определить, сколько существует пар оснований (b_1, b_2), для которых n! имеет ровно p конечных нулей в обеих системах счисления b_1 и b_2, где p — положительное целое число, не меньшее x.
Входные данные
Входной файл содержит 1000 строк данных. Каждая строка содержит два целых числа n (1 ≤ n ≤ 100000) и x (2 ≤ x ≤ 2500). Ввод завершается строкой, содержащей два нуля.
Выходные данные
Для каждой строки входных данных выведите одну строку с целым числом, обозначающим количество пар оснований (b_1, b_2), для которых n! имеет ровно p конечных нулей в обеих системах счисления, где p не меньше x. Вы можете быть уверены, что ни одно из выходных чисел не превысит 5·10^18.