×

# Beautiful Numbers - Codeforces problem doubt

 1 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 2★kuruma 17.5k●72●143●209 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)

 2 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, answered 26 Apr '13, 07:15 3★dolka1 146●3●6●9 accept rate: 33% 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 community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×249
×91
×42
×19

question asked: 26 Apr '13, 05:15

question was seen: 4,509 times

last updated: 29 Apr '13, 06:19