Nzec in AGS

[ankitiiita_sof]

my code works fine on ideone...... but gives runtime error in spoj...... plzzz help !!!

t=int(raw_input())
for x in range(0,t):
   a,d,r = raw_input().split()
   n,m = raw_input().split()
   a = int(a)
   d = int(d)
   r = int(r)
   n = int(n)
   m = int(m)
   r1=r**((n/2)-1)
   r2=r**(n/2)
   if(n%2==0):
         s=(a*r1) + ((d*(r2-1))/(r-1))
         print s%m  
   else:
         s=(a*r2) + ((d*r*(r2-1))/(r-1))
         print s%m

[numerix]

Ever thought of "division by zero"?

[ankitiiita_sof]

thnx for pointing out that error sir....... now i am getting TLE.... is there any better algorithm for this ???
better than O(1) ??

t=int(raw_input())
for x in range(0,t):
       a,d,r = raw_input().split()
       n,m = raw_input().split()
       a = int(a)
       d = int(d)
       r = int(r)
       n = int(n)
       m = int(m)
       r1=r**((n/2)-1)
       r2=r**(n/2)
       if(n%2==0):
             if(r==1):
               s=((a%m)+((((n%m)/2)*(d%m))%m))%m
             else:
               s=((((a%m)*(r1%m))%m) + ((((d%m)*((r2-1)%m))/(r-1))%m))%m
             print s 
       else:
             if(r==1):
               s=((a%m)+((((n/2)%m)*(d%m))%m))%m
             else: 
               s=((((a%m)*(r2%m))%m) + ((((d%m)*(r%m)*((r2-1)%m))/(r-1))%m))%m
             print s

[francky]

Your code is not really O(1)
r**n has a enormous cost and r**(n/2) has numerical issues.
You have to forgive this way and work modulo m all the way,
there is a O(log(n)) algorithm with 64bit arithmetic.

[ankitiiita_sof]

i have used modulo for r**((n/2)-1) ...... still it gives me TLE..... what can be better than a formula ???
@francky : do u mean i have to use repeated squaring algorithm for calculating r**n ???

t=int(raw_input())
for x in range(0,t):
       a,d,r = raw_input().split()
       n,m = raw_input().split()
       a = int(a)
       d = int(d)
       r = int(r)
       n = int(n)
       m = int(m)
       r1=(r%m)**(((n/2)-1)%m)
       r2=(r%m)**((n/2)%m)
       if(n%2==0):
             if(r==1):
               s=((a%m)+((((n%m)/2)*(d%m))%m))%m
             else:
               s=((((a%m)*(r1%m))%m) + ((((d%m)*((r2-1)%m))/(r-1))%m))%m
             print s 
       else:
             if(r==1):
               s=((a%m)+((((n/2)%m)*(d%m))%m))%m
             else: 
               s=((((a%m)*(r2%m))%m) + ((((d%m)*(r%m)*((r2-1)%m))/(r-1))%m))%m
             print s

[ankitiiita_sof]

plzz help ....

[francky]

Did you ever try (987654321)**(123456789) ????
Don't you think this only one computation could time out ?

You have to work in a very different way.
You can use an Algebraic method.
A 2×2 matrix and fast exponentiation can be usefull...
(for exemple)

[Hasil_Sharma]

Hi I am doing using a O(logn) algorithm for computing sum of terms. But still getting a TLE.
At first I made a 64 Bit solution but got TLE so converted it to integers, but still TLE. Kindly help me.
--code-snipped--
Edit(Francky)--> It was a C code, here is the Python section.