How can i solve this problem SPOJ.com - Problem AKVQLD02 in time please help
Thanx in advance
You should give more time prior to asking about the question’s solution…
http://www.spoj.com/status/japoorv/
You have just tried once till now, and ended up with TLE.
Please wait and try for few hours more, and still if you get errors, tell codechef community here. You would surely be helped…
It would be better if you try this first http://www.spoj.com/problems/FASTPOW/
and I think this would be helpful http://en.wikipedia.org/wiki/Modular_exponentiation#Right-to-left_binary_method
can anybody tell me what’s wrong ? i did it using modual exp right to left method
__author__ = 'Achut'
t = int(input())
while t:
t = t-1
a,b = input().split()
a,b = int(a),int(b)
if a is 0:
print(0)
continue
if b is 0 or a is 1:
print(1)
continue
bin = '{0:b}'.format(b)
bin = str(bin)
x = 1
for c in bin:
x = (x*x)%1000000007
if c is "1":
x = (a*x)%1000000007
print(x)
U should convert numbers to string and continuously modulo them and finally use fast power to compute. Here is a accepted code on SPOJ:
Hope it helps!!
Why is it that we need to convert both numbers to string? Doesn’t 10^18 fit in an ULL type?