Prev: Blender's UI toolkit?
Next: Looking for a visual basic programmer to do a quick debug
From: mukesh tiwari on 5 Feb 2010 15:08
Hello Everyone. I am trying to solve problem(http://www.spoj.pl/
problems/REC/) in python but getting time limit exceed. Could some one
please tell me how to optimize the program specially the power
function which i am using to calculate the last M digits of expression
A^n. Here is my code.
Thank you.



__author__="Mukesh Tiwari"
__date__ ="$Feb 5, 2010 6:53:20 PM$"

def power(A,N,M):
ret=1
while(N):
if(N%2!=0):ret=(ret*A)%M
A=(A*A)%M
N=N//2
return ret
def geosum(A,N,M):
ret=1
if(N==1):return 1
while(N>1):
if(N%2==0):
ret=(ret*(1+power(A,N//2,M)))%M
else:
ret=(ret*(1+power(A,N//2,M))%M)+power(A,N-1,M)%M
ret%=M;
N=N//2
return ret%M

if __name__ == "__main__":
n=input();
while(n):
l=raw_input()
k=l.split(" ")
#print k[0],' ',k[1],' ',k[2],' ',k[3]
A=int(k[0])
B=int(k[1])
N=int(k[2])
M=int(k[3])
print (power(A,N,M)%M+(B%M*geosum(A,N,M)%M)%M)%M
n-=1
 | 
Pages: 1
Prev: Blender's UI toolkit?
Next: Looking for a visual basic programmer to do a quick debug