Не работает операция остатка от 10**9+7(1000000007)
У меня есть код, находящий количество сочетаний (n,k). В результате мне нужно будет вернуть остаток числа от (10**9+7). Я решил ускорить программу, и добавить операцию остатка в функцию, получился вот такой код:
def combination(n, k):
if 0 <= k <= n:
m = 10**9+7
nn = 1
kk = 1
for t in range(1, min(k, n - k) + 1):
nn = (nn * n) % m
kk = (kk * t) % m
n -= 1
return nn // kk
else:
return 0
Но по непонятной мне причине, деление с остатком в функции не происходит и на выходе выдается огромное число. В чем проблема?
Ответы (1 шт):
Взятие по модулю нельзя проносить через деление: (a // b) % m != (a % m) // (b % m). Через сложение, вычитание и умножение можно, а через деление нельзя.
Пример для Cnk(9, 4) mod 19:
Cnk(9, 4) = (9 * 8 * 7 * 6) / (1 * 2 * 3 * 4) = 3024 / 24 = 126 Cnk(9, 4) % 19 = 12 (9 * 8 * 7 * 6) % 19 = 3024 % 19 = 3 (1 * 2 * 3 * 4) % 19 = 24 % 19 = 5 3 // 5 = 0 12 != 0
P.S. Для факториала особенно просто считается разложение на простые. На трёх разложениях дробь сокращается, затем считается произведение по модулю.
P.P.S. Расширенный алгоритм Евклида вычисляет обратное число по модулю. Его тоже часто используют для решения этой задачи - деление заменяется на умножение на обратный, а умножения делаются по модулю.