P5091 【模板】欧拉定理

gate

费马小定理：

当(a,pin mathbb Z)且(p)为质数，(a ot=0 pmod p) 时有：
(a^{p−1}equiv1 pmod p)

所以 (a^b equiv a^{bmod{p-1}} pmod p)

欧拉定理：

当 (a,min mathbb Z)，且 (gcd(a,m)=1)时有：
(a^{varphi(m)}equiv 1pmod{m})
（(varphi(x)) 是欧拉函数）

所以 (a^bequiv a^{bmod varphi(m)}pmod m)

扩展欧拉定理：

当 (a,min mathbb Z)，且 (gcd(a,m) ot=1)时有：
(a^bequiv egin{matrix} a^b&,b<varphi(m)pmod m \a^{bmodvarphi(m)+varphi(m)}&,bgevarphi(m)pmod m end{matrix})

---

代码如下

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

int a,m,b,fi;
bool flag;

int euler(int n) {
	int res = n,a = n;
	for(int i = 2; i*i <= a; i++)
		if(a%i == 0) {
			res = res/i*(i-1);
			while(a%i == 0) a /= i;
		}
	if(a > 1) res = res/a*(a-1);
	return res;
}

int read() {
	long long x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
		ch = getchar();
	while('0' <= ch && ch <= '9') {
		x = (x<<3) + (x<<1) + ch-'0';
		if(x >= fi) flag = true;
		x %= fi;
		ch = getchar();
	}
	return x;
}

int qpow(int a,int b) {
	long long ans = 1,base = a;
	while(b) {
		if(b&1) ans = (ans*base)%m;
		base = (base*base)%m;
		b >>= 1;
	}
	return ans;
}

int main() {
	scanf("%d%d",&a,&m);
	a %= m;
	fi = euler(m);
	b = read();
	if(!flag) printf("%d",qpow(a,b));
	else printf("%d",qpow(a,b+fi));
	return 0;
}