SPOJ Raise the power

general
1

How can i solve this problem SPOJ.com - Problem AKVQLD02 in time please help

Thanx in advance

2

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
3

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
4

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)
5

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!!

6

Why is it that we need to convert both numbers to string? Doesn’t 10^18 fit in an ULL type?