欧拉降幂

放一张看烂的图

欧拉降幂就是第一个和第三个公式了，第二种情况直接快速幂算

当与模数互质时，

当与模数不互质时，，这也就是广义欧拉定理

适用于幂次很大时，可以有效降低复杂度

在一些题中会出到无法用整型存下的范围，比如

这就必须用欧拉降幂了，边读入边处理

而且快速幂中的乘法可能会爆，有时要快速乘

模板：

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
ll a, mod; char s[A];
ll Euler(ll n) {
  ll ans = n;
  for (int i = 2; i * i <= n; i++)
    if (n % i == 0) {
      ans = ans / i * (i - 1);
      while (n % i == 0) n /= i;
    }
  if (n > 1) ans = ans / n * (n - 1);
  return ans;
}
ll fpow(ll a, ll b, ll ans = 1) {
  while (b) {
    if (b & 1) ans = ans * a % mod;
    a = a * a % mod; b >>= 1;
  }
  return ans;
}

int main(int argc, char const *argv[]) {
  while (scanf("%lld%s%lld", &a, s, &mod)) {
    int len = strlen(s); ll e = Euler(mod), ans = 0;
    for (int i = 0; i < len; i++) ans = (ans * 10 + s[i] - '0') % e;
    ans += e; printf("%lld\n", fpow(a, ans));
  }
  return 0;
}