P5091 【模板】欧拉定理

题目背景出题人也想写有趣的题面可惜并没有能力。题目描述给你三个正整数a,m,ba,m,b你需要求a^b \bmod mabmodm输入格式一行三个整数a,m,ba,m,b输出格式一个整数表示答案输入输出样例输入 #1 复制2 7 4输出 #1 复制2输入 #2 复制998244353 12345 98765472103312450233333333333输出 #2 复制5333说明/提示注意输入格式a,m,ba,m,b 依次代表的是底数、模数和次数样例1解释2^4 \bmod 7 224mod72输出2数据范围对于全部数据1≤a≤10^91≤a≤1091≤b≤10^{20000000}1≤b≤10200000001≤m≤10^61≤m≤106运用公式#include stdio.h #include iostream #include string using namespace std; typedef long long ll; int a,m,bm; int phi 1; string b; void Phi(){//计算小于m并且与m互质的个数 phi 1; int mm m; for(int i 2;i*i mm;i){ if(mm%i) continue; phi * (i-1); mm / i; while(mm%i 0){ phi * i; mm / i; } } if(mm 1) phi * (mm-1); return; } int qpow(int a,int p){ int ans 1; while(p){ if(p1) ans ((ll)(ans%m)*(a%m))%m; p 1; a ((ll)(a%m)*(a%m))%m; } return ans; } int main(){ int flag 0; cin a m b; a % m; Phi(); for(int i 0;i b.length();i){ bm bm*10(b[i]-0); if(bm phi) { flag 1; bm % phi; } } if(bm phi){ flag 1; bm % phi; } if(flag) bm phi; printf(%d\n,qpow(a,bm)); return 0; }