A^B%C ÒªÓÃC++д ÎÒÖ»»áC++

(A^B)%C

Time Limit:1000MS Memory Limit:65536K
Total Submit:263 Accepted:35 

Description 

Naruto' faith is never give up, so I hope you can persist in ACM. ACM is not a shortcut to success, there are many obstacles you should overcome, but only overcome them you can become more powerful ! 
First, you need to overcome English. Now this problem. 


Input 

The input consist of three integers A,B,C; 1<= A <=10000; 1<= B <=10^9; 1<=C<=10000; three 0 sign the end of the input.

Output 

The output will be a single integer——(A^B)%C. For example,A=2,B=4,C=5, then the result is (2^4)%5 = (2*2*2*2)%5 = 1.

Sample Input 


2 2 3
3 3 4
4389 99999999 1303
0 0 0


Sample Output 


1
3
698

---

Ç°Á½¸ö¶ÔÉÏÁË£¬µÚÈý¸öû¶ÔÉÏ£¬´úÂëÓ¦¸ÃûÓÐÎÊÌâ²Å¶Ô
ÊÔÁ˺ܶàÊý¾Ý£¬LZ¿´ÏÂÄãÌṩµÄÊý¾ÝºÍ´ð°¸¶¼Ã»ÎÊÌâÂð£¿
C/C++ code:
#include <iostream>
using namespace std:

typedef long unsigned int LUINT;

LUINT remainder(LUINT a, LUINT b, LUINT c)
{
a %= c;
bool bEven = (0==b%2);
LUINT tmp = a;
for (LUINT i=bEven?b:b-1; i>=2; i/=2)
{
a = (a*a % c);
}
return bEven? a%c : (a*tmp)%c;
}