提交记录

#include<bits/stdc++.h>
using namespace std;
const int A=1e9,M=1e8;
int a,m,b,phi,ans;
bool flag;

void Read(int &x)
{
	char t=getchar();
	x=0;
	while(t<'0'||t>'9')
	{
		t=getchar();
	}
	while(t>='0'&&t<='9')
	{
		x=x*10+t-'0';
		t=getchar();
	}
}

void Read_B(int &x)
{
	char t=getchar();
	x=0;
	while(t<'0'||t>'9')
	{
		t=getchar();
	}
	while(t>='0'&&t<='9')
	{
		x=x*10+t-'0';
		if(x>phi)
		{
			x%=phi;
			flag=1;
		}
		t=getchar();
	}
}

int Phi(int x)
{
	int sx=sqrt(x),counts,phi=1,tmp;
	for(int i=2;x!=1&&i<=sx;i++)
	{
		counts=0;
		tmp=x;
		while(!(x%i))
		{
			counts++;
			x/=i;
		}
		if(counts)
		{
			phi*=tmp/x/i*(i-1);
		}
	}
	if(x>1)//x is a prime
	{
		return x-1;
	}
	return phi;
}

int Pow(int x,int y)
{
	if(!y)
	{
		return 1;
	}
	return (y&1)?1ll*x*Pow(x,y^1)%m:Pow(1ll*x*x%m,y>>1);
}

int main()
{
	Read(a);
	Read(m);
	phi=Phi(m);
//	cout<<"phi="<<phi<<endl;
	Read_B(b);
	if(m==1)
	{
		printf("%d\n",0);
		return 0;
	}
	if(flag)
	{
		ans=Pow(a,b%phi+phi);
	}
	else
	{
		ans=Pow(a,b);
	}
	printf("%d\n",ans);
	return 0;
}
/*
8236420 17301570 3487152
//
4027180
*/