Geek asks and answers

Regarding the behavior of a modular operation?

I wrote the following program in python for the following codec 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 does not work correctly, for example, for values ​​n = 498 and r = 2, the response returned by combo () is 0, because q = 243293343 and r = 1428355228 how to execute my modulo operation in arr [] to fix this error ?

+3
source share
3 answers

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

(a / b)% MOD

(a * inverse (b))% MOD // You must find the inverse of b. To find the inverse of b, use Fermat’s theorem.

: a/b, MOD, b, a * b, MOD it.

0

a ^ b O (log (b)), , . :

       (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 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;
}

- .

, - , return (base * Power (base, expo-1)% mod)

, , expo , base ^ (expo-1), expo i.e. (expo-1) ,

.

Topcoder

wiki: expo by squaring

+1

, ,

return ((q/r)% mod)

1000000007, .. ,

= ( [] * [-])%

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

where is the power function

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 very helpful if someone explains the math using return (base * Power (base, expo-1)% mod)

0
source

More articles:


All Articles