洛谷 P5091 【模板】扩展欧拉定理

洛谷 P5091 【模板】扩展欧拉定理

思路

有扩展欧拉定理：

当(a,min)时有：

(a^bequiv a^{b ext{mod} phi(m) + phi(m)}( ext{mod} m)(bgeqphi(m)))

(a^bequiv a^b( ext{mod} m)(b < phi(m)))

前两个数直接读入，然后求(m)的欧拉函数，在读入(b)时边读入边取模即可

代码

/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

inline int qwq(int mod) {
	char c = getchar(); int x = 0, f = 1, flag = 0;
	for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
	for( ; isdigit(c); c = getchar()) {
		x = x * 10 + (c ^ 48);
		if (x > mod) x %= mod, flag = 1;
	}
	if (flag) x += mod;
	return x * f;
}

inline int mul(int a, int b, int mod) {
	int res = 0;
	while (b) {
		if (b & 1) res = (res + a) % mod;
		a = (a + a) % mod, b >>= 1;
	}
	return res;
}

inline int power(int a, int b, int mod) {
	int res = 1;
	while (b) {
		if (b & 1) res = mul(res, a, mod);
		a = mul(a, a, mod), b >>= 1;
	}
	return res;
}

int a, b, m;

signed main() {
	cin >> a >> m;
	int tmp = m, phi = m;
	for (int i = 2; i * i <= m; i++) {
		if (tmp % i == 0) {
			phi = phi - phi / i;
			while (tmp % i == 0) tmp /= i;
		} 
	}
	if (tmp > 1) phi = phi - phi / tmp;
	b = qwq(phi);
	cout << power(a, b, m);
	return 0;
}