【模板】欧拉定理

【题目描述】

给你三个正整数，(a)，(b)，(m)，求：(a^b ; mod ; m)。（题目传送门）

【题解】

由扩展欧拉定理即可解出该题：

[a^b equiv egin{cases}a^{b \, mod varphi(m)} & gcd(a,m) =1 \ a^b & c < varphi(m) \,, gcd(a,m) e 1 \ a^{(b \, mod varphi(m)) + varphi(m)} & c ge varphi(m) \,, gcd(a,m) e 1 end{cases} ]

• 计算(varphi(m))

• 边输入(b)边取模

• 分情况计算

(Code：)

#include<cstdio>
using namespace std;
#define ll long long
#define rg register
struct ios{
	template<typename TP>
	inline ios operator >> (TP &x)
	{
		TP f=1;x=0;rg char c=getchar();
		for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;
		for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
		x*=f;
		return *this;
	}
	template<typename TP>
	inline ios operator << (TP x)
	{
		int top=0,s[66];
		if(x<0) x=-x,putchar('-');
		if(!x) putchar('0');
		while(x) s[++top]=x%10+'0',x/=10;
		while(top) putchar(s[top--]);
		return *this;
	}
	inline ios operator << (char s)
	{
		putchar(s);
		return *this;
	}
}io;
int a,m,p,b,n,f;
inline int read()
{
	int x=0;rg char c=getchar();
	for(;c>='0' && c<='9';c=getchar())
	{
		x=(x<<3)+(x<<1)+(c^'0');
		if(x>=p) f=1,x%=p;
	}
	if(x>=p) f=1,x%=p;
	return x;
}
inline int pow(int a,int b)
{
	int ans=1;
	for(;b;b>>=1)
	{
		if(b&1) ans=(ll)ans*a%m;
		a=(ll)a*a%m;
	}
	return ans%m;
}
int main()
{
//	freopen("testdata.in","r",stdin);
	io>>a>>m,p=n=m;
	for(rg int i=2;i*i<=n;++i)
	{
		if(n%i==0)
		{
			p=p/i*(i-1);
			while(n%i==0) n/=i;
		}
	}
//	io<<p<<' '<<n<<'
';
	if(n>1) p=p/n*(n-1);
//	io<<p<<'
';
	b=read();
	if(f) b+=p;
//	io<<b<<'
';
	io<<pow(a,b);
	return 0;
}