【题目来源】
洛谷：P5091 【模板】扩展欧拉定理 - 洛谷
【题目描述】
给你三个正整数，\(a,m,b\)，你需要求：\(a^b \bmod m\)
【输入】
一行三个整数，\(a,m,b\)
【输出】
一个整数表示答案
【输入样例】
2 7 4
【输出样例】
2
【解题思路】
【算法标签】
《洛谷 P5091 扩展欧拉定理》 #数学# #模板题#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
#define int long long
int a, m, cnt, r, ans;
string b;// 计算欧拉函数φ(m)
int phi(int x)
{int res = x;for (int i = 2; i * i <= x; i++)if (x % i == 0){res = res * (i - 1) / i; // φ(n) = n * ∏(1 - 1/p)while (x % i == 0)x /= i; // 去除所有i因子}if (x != 1) // 处理剩余的质因子res = res * (x - 1) / x;return res;
}// 大数取模
int mod(string s, int div)
{int rem = 0;for (int i = 0; i < s.size(); i++)rem = (rem * 10 + (s[i] - '0')) % div;return rem;
}// 比较两个大数（字符串形式）
bool cmpBIG(string x, string y)
{ if (x.size() > y.size())return true; // x >= yif (x.size() < y.size())return false; // x < yreturn x >= y; // 长度相等时比较字典序
}// 快速幂
int qmi(int a, int b, int p)
{int mul = 1;a %= p;while (b){if (b & 1) mul = mul * a % p;a = a * a % p;b >>= 1;}return mul;
}signed main()
{cin >> a >> m >> b; // 输入a, m, b（b是大数，用字符串表示）a %= m; // 先对a取模cnt = phi(m); // 计算欧拉函数φ(m)r = mod(b, cnt); // 计算b mod φ(m)// 如果b >= φ(m)，则需要加上φ(m)（扩展欧拉定理）if (cmpBIG(b, to_string(cnt)))r = (r + cnt) % m; // 应该是(r + cnt) % cnt，但这里写错了ans = qmi(a, r, m); // 计算a^r mod mcout << ans << endl;return 0;
}
【运行结果】
2 7 4
2