modulo problem

general
1

how to calculate ((2^n)/3)%1000000007…
if n can be as large as 10^18…

2

First calculate 2^n using modular exponentiation( Code is given below), let this value be x,

Here’s the link containing the algorithm : click here

You can perform division in modulo by calculating the modular multiplicative inverse of 3, let this value be y.

Now calculate (x*y)%1000000007

Here’s the code for calculating multiplicative inverse:

long long int inv(long long int a) {
return pow_(a,mod-2,mod);
}

Here pow_ is the function for modular exponentiation:

 #define mod 1000000007
 long long int pow_(long long int base,long long int exp,long long int m)
 {
  long long int ret=1;
   base%=m;
   while(exp)
   {
     if(exp&1)
      {
       ret*=base;
       ret%=m;
      }
      base*=base;
      base%=m;
      exp>>=1;
    }
   return ret%m;
 }
1 Like
3

hey its not working ans for n=34 should be 726623026 but its not going this way… :frowning:

4

Since you are dividing 2^n by 3 you need to perform the multiplication of 2^n by the modular inverse of 3%1000000007.

Since 3 is a prime number, you can use Fermat’s Little Theorem to calculate the inverse as:

3^1000000005 % 1000000007 = 333333336

Then you can multiply it with 2^34 % 1000000007 and get your final result.

I’m getting 59956355 in Python…

5

How did you calculate this answer? Show me your code.

6

You can also see the question WCOUNT in easy section.
Multiplicative inverse was used in this question.
I have used this method and got AC in this question.