C++ 代码
#include<iostream>
using namespace std;
typedef long long ll;
const int MOD=998244353;
int a;
ll b;
int qmi(int a,ll b){
int res=1;
while(b){
if(b&1) res=(ll)res*a%MOD;
a=(ll)a*a%MOD;
b>>=1;
}
return res;
}
int main(){
cin>>a>>b;
ll res=a;
int x=a;
if(a==1) cout<<0<<endl;
else{
for(int i=2;i<=x/i;i++){
if(x%i==0){
while(x%i==0){
x/=i;
}
res=res/i*(i-1);
}
}
if(x>1) res=res/x*(x-1);
res=res*qmi(a,b-1)%MOD;
cout<<res<<endl;
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla