题目类型:快速幂
思路
1.计算得出a的b次方是多少(快速幂主要步骤)
因为a的b次方很大,所以要用到快速幂
2.得出有多少个x
3.把x%mod
注意:要进行特例判断(2组)
正解代码
#include<bits/stdc++.h> //万能头文件
using namespace std;
typedef long long ll; //避免多次写long long
const ll mod=998244353; //定义mod的数
ll qmod(ll a,ll n)
{
ll res=1;
while(n)
{
if(n&1)
res=(res*a)%mod;
n>>=1,a=(a*a)%mod;
}
return res;
}
ll divide(ll a,ll b)
{
return a*qmod(b,mod-2)%mod;
}
int main()
{
ll a,b;
cin>>a>>b; //输入
if(a==1)
{
cout<<"0";
return 0;
}
//进行特例判断
if (a==mod&&b==1)
{
cout<<mod-1;
return 0;
}
//进行特例判断
ll res=qmod(a,b);
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
res=res*divide(i-1,i)%mod;
while(a%i==0)
a/=i;
}
if(a!=1)
res=res*divide(a-1,a)%mod;
cout<<res; //输出%mod后的结果
return 0; //好习惯
}