>>13624966the thing you seem not to understand is the algorithm to calculate a^b in O(log b) instead of O(b)
what one would normally come u with is:
res = 1
for i in range(b):
res *= a
which calculates a * a * a * ... * a b times
but as some of the people already said
a^b = a^2 * a^(b/2)
so lets say we have b = 11
a ^ b = a ^1 * a^2 * a^8
because 1 + 2 + 8 = 11
11 in binary form is 1011
looking at the binary representation from right to left you see to exponents of 2 to be
8 4 2 1
1 0 1 1 = b
division by 2 in binary is the same as right shift
11/2 = 5 (its 5.5 but we dont need the remainder so integer division is used)
1011 >> 1 = 101 = 5 in decimal numbers
so how do we calculate that with a computer program?
res = 1
while b > 0:
if (b % 2 == 1) res *= a
b /= 2
a *= a
lets analyze this step by step
take a = 7 and b = 11 and res = 1
first iteration:
b is odd so res *= a = 7
b /= 2 = 5
a *= a = 49
second it:
b = 5 is odd so res *= a = 7 * 49 = 343
b /= 2 = 2
a *= a = 2401
third:
b = 2 is even
b /= 2 = 1
a *= a = 5,764,801
fourth:
b = 1 is odd so res *= a = 1,977,326,743
b /= 2 = 0
a *= a = something (b is zero so we dont have to calculate this)
in your task there is a modulo operation, it all still works but using some number theory basics you should understand that if
a = b mod n
and
c = d mod n
then
ac = bd mod n
