Самый быстрый способ умножения больших чисел на python?

Question

Взгляните на следующий код:

total = 0
for j in range(int(start)-1,int(end)):
    total += (A+j)*(B+j)*(C+j)*(D+j)
print(total%1000000007)

Теперь код работает нормально, но мне нужно уменьшить сложность времени.

1 <= A, B, C, D <= 10 ^ 5 </p>

1 <= начало <= конец <= 10 ^ 5 </p>

Как видите, числа могут быть очень большими. Как я могу ускорить часть умножения? Я попробовал русскую крестьянскую технику. Это все еще не достаточно быстро.

Также я читал похожие посты по умножению python, но это не могло решить мою проблему.

Answer 1

Я думаю, для этого достаточно вспомнить, что (a+b)%c = a%c +b%c

Поскольку каждая часть l oop не очень большая, вы можете попробовать:

total = 0
for j in range(int(start)-1,int(end)):
    total = (total + (A+j)*(B+j)*(C+j)*(D+j)) %1000000007
print(total)

Answer 2

Здесь вы можете использовать модульную арифметику c.

(a+b)%c=(a%c+b%c)%c

(a∗b)%c=((a%c)∗(b%c))%c

(a−b)%c=((a%c)−(b%c)+c)%c

(a/b)%c=((a%c)∗(b−1%c))%c

Это обеспечит целочисленное переполнение и сохранит сложность времени.