PRoblem Description

Given A,B,C, You should quickly calculate the result of A^B mod C. (1<=A,B,C<2^63).

Input

There are multiply testcases. Each testcase, there is one line contains three integers A, B and C, separated by a single space.

Output

For each testcase, output an integer, denotes the result of A^B mod C.

Sample Input

Sample Output

Source

為了防止相乘溢出，所以就用加減來實現，此外這個oj不支持%lld 我在這里也出錯了幾次，大家要注意哦 ??！

#include<stdio.h>using namespace std;#define ll long longll mulmod(ll a,ll b,ll c){    ll ans=0;    while(b)    {        if(b&1)        {            ans+=a;            if(ans>=c) ans-=c;        }        a<<=1;        if(a>=c)  a-=c;        b>>=1;    }    return ans;}ll quickmod(ll a,ll b,ll c){    ll ans=1;    while(b)    {        if(b&1)           ans=mulmod(ans,a,c);//這樣寫是為了使a*ans和a*a不溢出        a=mulmod(a,a,c);        b>>=1;    }    return ans;}int main(){    ll a,b,c ;    while(~scanf("%I64d%I64d%I64d",&a,&b,&c))    {        a=a%c;        printf("%I64d/n",quickmod(a,b,c));    }    return  0;}