SPOJ Raise the power

How can i solve this problem http://www.spoj.com/problems/AKVQLD02/ in time please help

Thanx in advance

You should give more time prior to asking about the question’s solution… :slight_smile:
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… :slight_smile:

1 Like

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

2 Likes

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?

//