Доброго времени суток.
Есть задание:
Вычислить последние 12 знаков следующего выражения(** - возведение в степень):
A * B**C + D
Где,
1 <= A, B, C, D <= 10**9
Вот моя реализация на Python:
n = int(input()) #number of test cases
module = 10 ** 12
def pow_l(x, n):
result = 1
while n != 0:
if n % 2 != 0:
result *= x
result %= module
n -= 1
else:
x *= x
x %= module
n /= 2
return result
for i in range(n):
a, b, c, d = (int(num) for num in input().split())
prod = (a * pow_l(b, c) + d) % module
print (str(prod).zfill(12))
Но, увы, этот алгоритм слишком медленный. Что можете посоветовать?
Буду очень благодарен за помощь.
