「Note」扩展欧拉定理

真是令人自闭。

$\mathcal{Theorem}$

$$ a^x\equiv \begin{cases} a^{x\bmod\varphi(m)} & (a,m)=1 \\ a^{x\bmod\varphi(m)+\varphi(m)} & (a,m)\neq1,x\ge\varphi(m) \end{cases} \pmod m $$

$\mathcal{Pro}$

writing…

$\mathbb{CF17D \ Notepad}$

$\mathcal{Link}$

link

$\mathcal{Sol}$

就是求 $b ^ {n - 1} \times (b - 1) \ \mathrm{mod} \ c$。
那么套上去就行。

$\mathcal{Code}$

#include <cstdio>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;

int b, n, c, phi, tmp, ans, flag;
string bs, ns;

void read(int& x, int Mod, string str) { 
	flag = 0; 
	for (int i = 0; i < str.length(); i++) x = ((x << 3) + (x << 1) + (str[i] ^ 48)), flag |= (x >= Mod), x %= Mod;  
}

int qpow(int x, int y, int Mod) {
	int res = 1;
	while (y) {
		if (y & 1) res = res * x % Mod;
		x = x * x % Mod, y >>= 1;
	}
	return res;
}

signed main() {

	cin >> bs >> ns >> c, tmp = phi = c, read(b, c, bs);
	
	for (int i = 2; i * i <= tmp; i++) if (tmp % i == 0) {
		phi = phi / i * (i - 1);
		while (tmp % i == 0) tmp /= i;
	}
	if (tmp > 1) phi = phi / tmp * (tmp - 1); read(n, phi, ns);

	ans = ((b - 1) * qpow(b, (n - 1) % phi + flag * phi, c) % c + c) % c;
	printf("%lld\n", ans ? ans : c);

	return 0;
}