P5091 【模板】欧拉定理

(color{#0066ff}{ 题目描述 })

给你三个正整数，(a,m,b),你需要求： (a^b mod m)

(color{#0066ff}{输入格式})

一行三个整数，(a,m,b)

(color{#0066ff}{输出格式})

一个整数表示答案

(color{#0066ff}{输入样例})

2 7 4
    
998244353 12345 98765472103312450233333333333

(color{#0066ff}{输出样例})

2
    
5333

(color{#0066ff}{数据范围与提示})

注意输入格式，(a,m,b) 依次代表的是底数、模数和次数

样例1解释：
(2^4 mod 7 = 2)
输出2

数据范围：
对于全部数据：
(1≤a≤10^9)
(1≤b≤10^{20000000})
(1≤m≤10^6)

(color{#0066ff}{ 题解 })

其实就一个式子。。。

[left{egin{aligned}a^b equiv a^b mod m b < varphi(m) \ a^bequiv a^{b mod varphi(m)+varphi(m)} bgevarphi(m)end{aligned} ight. ]

#include<bits/stdc++.h>
#define LL long long
LL in() {
	char ch; LL x = 0, f = 1;
	while(!isdigit(ch = getchar()))(ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 1) + (x << 3) + (ch ^ 48));
	return x * f;
}
LL ksm(LL x, LL y, LL mod) {
	if(x == 0) return 0;
	LL re = 1LL;
	while(y) {
		if(y & 1) re = re * x % mod;
		x = x * x % mod;
		y >>= 1;
	}
	return re;
}
int getphi(int x) {
	int res = x;
	int phi = x;
	for(int i = 2; i * i <= x; i++) {
		if(res % i == 0) {
			while(res % i == 0) res /= i;
			phi = phi / i * (i - 1);
		}
	}
	if(res > 1) phi = phi / res * (res - 1);
	return phi;
}
int main() {
	LL a = in(), m, b;
	LL phi = getphi(m = in());
	char ch;
	while(!isdigit(ch = getchar()));
	bool flag = false;
	for(b = ch ^ 48; isdigit(ch = getchar()); b = (b << 1LL) + (b << 3LL) + (ch ^ 48)) if(b >= phi) flag = true, b %= phi;
	printf("%lld
", ksm(a, (flag? b + phi : b), m));
	return 0;
}