FZU 1759

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

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

3 2 4
2 10 1000

Sample Output

1
24

题目大意：
给出a,b,c，求a ^ b mod c 的值。

解题思路：
我们看到B的范围是1e1000000，普通快速幂一定会超时，看到这个B我们应该用欧拉降幂把幂指数降下来。先上欧拉降幂板子：

inline ll ol(ll x)
{
	ll res=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			res-=res/i;
			while(x%i==0)
			  x/=i;
		}
	}
	if(x>1)
	  res-=res/x;
	return res;  
}

这是降幂公式，我们根据这个公式把指数降低，然后再套快速幂的板子，因为B的值太大，我们用字符串存B，然后求出B mod phi（c）的值，再用快速幂。AC代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline ll ol(ll x)//欧拉降幂模板
{
	ll res=x;
	for(int i=2;i*i<=x;i++)
	{
		if(x%i==0)
		{
			res-=res/i;
			while(x%i==0)
			  x/=i;
		}
	}
	if(x>1)
	  res-=res/x;
	return res;  
}
inline ll fastpow(ll a,ll b,ll c)
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		  ans=(ans*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	ll a,c;
	string b;
	while(cin>>a>>b>>c)
	{
		ll mod=ol(c);
		ll s=0;
		for(ll i=0;i<b.length();i++)//mod的过程
		  s=(s*10+b[i]-'0')%mod;
		s+=mod;
		ll ans=fastpow(a,s,c);
		cout<<ans<<endl;  
	}
	return 0;
}