2^n modulus 10^9+7

general
1

how to find the 2^n with n<=10^14
and modulus it by 10^9+7

2 Likes
2

Hello, you can do it by : “modular exponentation by squaring”, you can look about it here : Modular exponentiation - Wikipedia

Best,

Chaitanya.

3

can we use BigInteger in java to calculate (2^(10^14))%m…???

where m = 10^9+7

1 Like
4

Try this tutorial this will be really helpful for you.

http://discuss.codechef.com/questions/36870/cake-walk

2 Likes
5

use repeated squaring with mod

time complexity : O(logN)

  long long int cal(long long int N,long long int pow,long long int MOD){


      if(N==0 || N===1) return N%MOD;

      if(pow==0) return 1;

       if(mod==1) return 0;

      long long int ans=1;

        while(pow){

            if(pow%2){

               ans=(ans*N)%MOD;
            }

            N=(N*N)%MOD;
            pow/=2;
        }
    return ans;
  }

HAPPY CODING

1 Like
6

Perfer my code school modular exponentiation video . its help you .

2 Likes
7

you can use the fast exponentiation method to find such big powers of N

refer to this wiki link:
Exponentiation by squaring - Wikipedia

or use pythons inbuilt function pow()…

1 Like
8

also find the a^b for very large a and b a,b<=10^14

9

In general you can find a ^ b by using : “exponentation by squaring” : Exponentiation by squaring - Wikipedia

10

pow() function of python is great… thanks man

1 Like