You are not logged in. Please login at www.codechef.com to post your questions!

×

SPOJ Raise the power

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

Thanx in advance

asked 29 May '14, 20:00

japoorv's gravatar image

5★japoorv
29592356
accept rate: 0%


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

link

answered 29 May '14, 20:18

achaitanyasai's gravatar image

5★achaitanyasai
2.2k61748
accept rate: 10%

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.. :)

link

answered 29 May '14, 20:03

skbly7's gravatar image

2★skbly7
1.9k91724
accept rate: 8%

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

answered 29 May '14, 20:48

achut1993's gravatar image

3★achut1993
6628
accept rate: 16%

U should convert numbers to string and continuously modulo them and finally use fast power to compute. Here is a accepted code on SPOJ:

http://ideone.com/U0S4VM

Hope it helps!!

link

answered 30 May '14, 02:32

tarun018's gravatar image

4★tarun018
8127
accept rate: 0%

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

(30 May '14, 03:44) kuruma3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×18

question asked: 29 May '14, 20:00

question was seen: 1,430 times

last updated: 30 May '14, 03:44