Wednesday, February 10, 2010

Big Mod




Calculate
R:=BP
mod M, meaning remainder R when B raised to the power of P is divided by M.

for large values of B, P, and M using an efficient algorithm.
(That's right, this problem has a time dependency !!!.)


Input



Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.


Output



The result of the computation. A single integer.


Sample Input



3
18132
17

17
1765
3

2374859
3029382
36123


Sample Output



13
2
13195

// Big-Mod.cpp : Defines the entry point
for the console application.



//



 







#include "stdafx.h"



int _tmain(int argc, _TCHAR* argv[])
{
                void
bigmod(long int x,long int y,long int z);
                long int B,P,M;
                while(cin>>B)
                {
                                cin>>P;
                                cin>>M;
                                bigmod(B,P,M);
                }
                return 0;
}
void bigmod(long int x,long int y,long int z)
{
                int pow,rem;
                rem=x%z;
                for(pow=1;pow<y;pow++)
                {
                                rem=(rem*(x%z))%z;
                }
                cout<<rem<<endl;
}

No comments:

Post a Comment