regarding behaviour of modulo operation?

Question

I wrote the following program in python for the following codechef question http://www.codechef.com/problems/MOVES/

import sys tokenizedInput = sys.stdin.read().split() mod=1000000007 arr=[1]*5001 for i in range(1,5001): arr[i]=(arr[i-1]*i)%mod def combo(r,n,mod): q=arr[n] print q r=(arr[r]*arr[n-r]) print r return ((q/r)%mod) elm=0 for i in range (0,5001): n=int(tokenizedInput[elm]) elm=elm+1 k=int(tokenizedInput[elm]) elm=elm+1 if(n==0 and k==0): break out=0 if(((k-1)/2)!=(k/2)): out=(2*combo((k-1)/2,n-2,mod)*combo(k/2,n-2,mod))%mod else: out=(2*combo(k/2,n-2,mod)**2)%mod print out

but my modulo function is not working correctly for example for values n=498 and r=2 the answer returned by combo() is 0 because q=243293343 and r=1428355228 how to perform my modulo operation in arr[] to rectify this error ?

Chandan Mittal · Accepted Answer · 2014-04-20 12:28:16Z

The above power function calculates a^b in O( log(b) ) by using what is called as exponentiation by squaring. The idea is very simple:

 (a^2)^(b/2) if b is even and b > 0 a^b = a*(a^2)^((b-1)/2) if b is odd 1 if b = 0

This idea can be implemented very easily as shown below:

/* This function calculates (a^b)%c */ int modulo(int a,int b,int c) { long long x=1,y=a; while(b > 0) { if(b%2 == 1) { x=(x*y)%c; } y = (y*y)%c; // squaring the base b /= 2; } return x%c; }

The above power function is just a recursive way of doing this. and as you asked about this

but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)

this is the same as checking if expo is odd then multiplying base with base^(expo-1) so that the new expo i.e. (expo-1) will become even and repeated squaring can be done

For more info refer:

Topcoder Tutorial

wiki: expo by squaring

sp1rs · Accepted Answer · 2014-02-04 16:25:45Z

When we divider (a/b)%MOD , then we do something like this .

(a/b)%MOD

(a*inverse(b))%MOD // You have to find the inverse of b. To find the inverse of b use Fermat Theorem.

Note never divide a/b and then take MOD , first find the inverse of b and then do a*b and then MOD it .

Community · Accepted Answer · 2020-06-20 09:12:55Z

Got the solution,Answering my own question , but search for an optimized version is encouraged the error was

return ((q/r)%mod)

is wrong for mod being 1000000007 ie a prime number , it has to be written as

r=(arr[r]*arr[n-r])%mod

return (q*Power(r,mod-2))%mod

where Power function is

def Power(base,expo): if(expo==0): return 1 else: if(expo&1): return(base*Power(base,expo-1)%mod) else: root=Power(base,expo>>1) return(root*root%mod)

but it will be of great help if anyone explains the mathematics behind using return(base*Power(base,expo-1)%mod)

Collectives™ on Stack Overflow

regarding behaviour of modulo operation?

3 Answers 3

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Related