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

×

Beautiful Numbers - Codeforces problem doubt

The problem is this:

http://codeforces.com/problemset/problem/300/C

Thanks to it, I managed to understand a bit better the usage and concept of modular multiplicative inverse.

Namely, if we want to compute x^(-1) % (M=a big prime number) then we can use Euler's Theorem and do:

x^(M-2) % M and compute it by fast exponentiantion, is this so?

However, many contestants there used this function:

long long int big_mod(long long int i, long long int j)
{
    if(j==0)
        return 1;
    long long int x=big_mod(i,j>>1);
    x=(x*x)%mod;
    if(j&1)
        return (x*i)%mod;
    return x;
}

My doubt is:

Is this function doing the same job as the standard fast exponentiation function? If not, why?

Thanks in advance,

Bruno

asked 26 Apr '13, 05:15

kuruma's gravatar image

2★kuruma
17.5k72143209
accept rate: 8%

it was a nice learning from the last contest, although I was unable to solve it in the time constraints.

(26 Apr '13, 15:58) bugkiller3★

The function calculates (a^b)%mod, because (a^b)%mod = ((a^(b/2)) * (a^(b/2)) % mod) if exponent b is even number, else if b is odd, (a^b)%mod = ((a^[b/2])%mod)((a^[b/2])%mod)(a%mod) ([x] is floor function)

That the function can calculate (a^b)%mod like this way is based on the fact (a*b)%mod = ((a % mod) * (b%mod))%mod.

By the way, if we use extended euclid algorithm, we can also calculate multiplicative inverse faster.

If a is inverse of x, then ax = 1 (mod N), that means ax-Ny=1. in this problem N(1000000007) is a prime number, the equation ax-Ny=1 has always a solution.

def ext_gcd(a, b):
    if b==0:
        return (1, 0)
    else:
        x, y = ext_gcd(b, a%b)
        return (y, x-(a/b)*y)
def mod_inv(a,N):
    x, y = ext_gcd(a, N)
    if x < 0:
        return (x+N)%N

cheers,

link

answered 26 Apr '13, 07:15

dolka1's gravatar image

3★dolka1
146369
accept rate: 33%

edited 26 Apr '13, 08:18

So, basically, that function is doing the same job as a standard fast exponentiation function, yes?

(26 Apr '13, 13:18) kuruma2★

The function calculates (a^b) mod M in O(logb). if "standard fast exponentiation function" points to the function which calculates a^b in log time, the function and the standard function do the same job

(29 Apr '13, 06:19) dolka13★
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:

×282
×91
×42
×19

question asked: 26 Apr '13, 05:15

question was seen: 4,524 times

last updated: 29 Apr '13, 06:19