Deanamic_Programming's blog

Modulus operation with long longs
By Deanamic_Programming, history, 7 years ago, In English

Hello everyone.
On yesterday's contest I implemented a exponentiation function. 

long long pow(long long n, long long k) {  
        n %= MOD;  
	if(k == 0) return 1;  
	if(k&1) return (n*(pow(n*n, k/2))%MOD)%MOD;  
	return pow(n*n, k/2) %MOD;  
}  

long long get(long long n) {  
	long long t = (n * pow(2, n-1));  
	t %= MOD;  
	return t;  
}

Which for some reason it returning a double when the exponent is high enough.
Why could this be?

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Click

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

This happened because there is pow function in cmath(it returns double). That's why it's better to name function bin_pow(for example).

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It mixed with std's pow, click

→ Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That happen because c++ standard library includes its own pow, and this pow receive two double parameters, so when you call it pow( 2, 30 ) match with c++ function, so if you use cast (see previous comment) pow( 2LL, 30LL ) match with your implemented function.

→ Reply