Для заданного числа A найдите наименьшее целое число B такое, что A делит B! (B factorial)

Question

A Дается так, что A = X^Y для некоторых положительных X и Y.

Ограничения:

1 <= Y <= 30000 
1 <= X <= 1000000000 (10^9) 

Test Cases

X = 2 and Y = 2. 
Minimum value of B is 4 (as B! = 4! = 24, A = X^Y = 4 and B! % A = 24 % 4 = 0) 

X = 2 and Y = 3. 
Minimum value of B is 4 (as B! = 4! = 24, A = X^Y = 8 and B! % A = 24 % 8 = 0) 

X = 1000000000 and Y = 30000. 
Minimum value of B is 1080015 

Ссылка на вопрос: https://codefights.com/challenge/XPjFvvKW4kk35jeLp

Answer 1

Вы можете ФАКТОР X^Y. Первый фактор X:

X = p1^e1 * ... * pk^ek 

Тогда X^Y будет:

X^Y = p1^(e1*Y) * ... * pk^(ek*Y) 

Тогда вы могли бы бинарный поиск B: для фиксированного значения, узнать, сколько раз каждый простой фактор p из X^Y появляется в B!. Это равно:

floor(B/p) + floor(B/(p^2)) + ... 

Что можно реализовать так:

count(B, p): 
    s = 0 

    while B != 0: 
     s += B/p 
     B /= p 

    return s 

Если эта функция возвращает >= ei*Y для каждого простого фактора pi из X^Y, это B значение жизнеспособно: уменьшить поиск в ниже, чтобы увидеть, можете ли вы найти меньший. В противном случае уменьшите поиск до верхней половины.

Заявление о проблемах говорит, что B будет вписываться в целое число, допустим, 64-разрядный. Это означает, что не более 64 итераций бинарного поиска. X до 10^9 может иметь только около 20 основных факторов, а функция count работает в O(log B). Поэтому ожидаем сделать около 64*20*64 операций, а также несколько необходимых для начальной факторизации. Должно работать очень быстро.