По заданному числу N определить максимальную степень числа K, которая делит N! (нацело)

235

15 декабря 2016, 16:08

Ограничение времени: 1 с
Ограничение реального времени: 5 с
Ограничение памяти: 64М

Задание:
По заданному числу N определить максимальную степень числа K, которая делит N! (нацело).

Формат входных данных:
Первая строка содержит одно число T (1 ≤ T ≤ 1000) (количество тестовых случаев).
Следующие T строк содержат по 2 числа N (1 ≤ N ≤ 1,000,000,000) и K (2 ≤ K ≤ 100), разделенных пробелом.

Формат результата:
Для каждого тестового случая в отдельной строке выведите максимальную степень.

Примеры:

Входные данные:

5 2

2 3

выход (он происходит сразу после ввода 5 2, например 3):

Подскажите алгоритм, пожалуйста, весь код не надо, кусочек можно. :)

Если считать факториал, допустим, макс. числа 1,000,000,000, то умрет компьютер + время. Мне сказали, что можно через разложение на простые множители, но я не совсем понимаю как. Заранее благодарен!

P.S. Любой другой алгоритм тоже с удовольствием рассмотрю!

Answer 1

Число K раскладываем на множители в виде число-степень:

4 -> (2:2)
10 -> (2:1, 5:1)
12 -> (2:2, 3:1)

(в коде это будет просто массив структур).

Дальше в цикле от 2 и до N делим текущее число последовательно на все основания, сколько можно.

N = 5, K = 6 (2:1, 3:1)
2 - будет только один раз делиться на 2 (1,0)
3 - только один раз на 3  (1,1)
4 - два раза на два (3,1)
5 -  не делиться

В скобках я показал "счет" по каждому делителю.

Теперь только осталось посчитать, результат. Так как в моем случае K раскладывается на множители в первой степени, то достаточно взять минимальное в конечном массиве. В общем случае, нужно поделить нацело "попарно" и взять минимум.

Пример номер два. K=12 (2:2, 3:1), N = 10

2 -> (1,0)
3 -> (1,1)
4 -> (3,1)
5 -> (3,1)
6 -> (4,2)
7 -> (4,2)
8 -> (7,2)
9 -> (7,4)
10 -> (8,4)

(8,4) / (2,1) = (4,4). Минимум равен 4. Значит 10! делиться на 12 в степени 4

Answer 2

Корректирую свой ответ из похожей темы

Если число p простое, то из теории чисел (разложение факториала) следует, что

N!#p = [N/p] + [N/p2] + ... + [N/pt], где:

[a] - целая часть числа a,
a#p - показатель простого числа p в каноническом разложении числа a.

При этом t = [logp N], а практически

t= [ln(N+0.5) / ln p]

В нашем случае K - составное, т.е. имеет каноническое разложение вида

K=p0r0 * p1r1 ... * psrs,

алгоритм факторизации можно выбрать по вкусу (для обеспечения быстродействия простые множители проверять при условии pi2 <= K, а если множитель pi найден, то этот и последующие множители искать у меньшего числа K/pi, соответственно сужая диапазон поиска).

Поэтому

deg = mini=0...s{[N!#pi / ri]}.