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

×

How to calculate a^b mod p i.e.(a^b%p) where p is a big prime number of the order 10^9....

i have some knowldege of fermats little theorem but for that i think 'b' must be of the form : b=k*(p-1) + m...and the answer would be a^m...but in my case 'b' is smaller than p for example b is 10^7(so i cant express 'b' in terms of 'p') ...?? By simply writing the expression it is overflowing the long long int range ..plz help

asked 12 May '15, 11:28

gagan86nagpal's gravatar image

5★gagan86nagpal
11116
accept rate: 11%


you can use repeated squaring it basically depends on the fact

alt text

you can use code:-

int mod = 1000000007
int powmod(int base,int pow)
{
   int res=1;
   while(pow)
   {     
         if (pow%2!=0)  res=(res*base)%mod;
         base=(base*base)%mod;
         pow/=2;
   }
   return res;
}

you can get more information from wiki-Exponentiation by squaring

link

answered 12 May '15, 12:47

sagarpatel's gravatar image

4★sagarpatel
822
accept rate: 0%

MOD 1000000007

int expo(int base,int power) { int result=1; while(power) { if(power&1) result=(resultbase)%MOD; base=(basebase)%MOD; power>>=1; } return result;

}

link

answered 12 May '15, 15:42

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

for large prime, replace int with long long

(12 May '15, 15:46) dragonemperor3★

MOD 1000000007 int square(int a) { return (aa)%MOD; } int expo(int base,int power) { if(power==1) return base; else if(power&1) return (baseexpo(base,power-1)) % MOD; else return square(expo(base,power/2))%MOD;

}

link

answered 12 May '15, 15:45

dragonemperor's gravatar image

3★dragonemperor
89321134
accept rate: 10%

for large prime, replace int with long long

(12 May '15, 15:46) dragonemperor3★
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:

×626
×336
×48
×7

question asked: 12 May '15, 11:28

question was seen: 5,193 times

last updated: 12 May '15, 15:46