Modular Exponentiation September 4, 2010

Problem5

CodeChef

ACCEPTED

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
using namespace std;
int  main()
{
 int A,B;
 while(1)
 {
 scanf("%d%d",&A,&B);
 if(A==0&&B==0) break;

 int base,power,modulus;
 modulus=1000000;
 base=A;power=B;
 long long result = 1;
 for (int i = 31; i >= 0; i--) {
 result = (result*result) % modulus;
 if ((power & (1 << i)) != 0) {
 result = (result*base) % modulus;
 }
 }

 int ans=(int) result;

 printf("%d\n",ans);
 }


return 0;
}

Advertisement