AcWing 4968. 互质数的个数
原题链接
中等
作者:
最后五分钟
,
2024-04-11 16:33:42
,
所有人可见
,
阅读 5
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using namespace std;
const int N=1010,p=998244353;
typedef pair<int,int> PII;
int qmi(int a,int b)
{
int res=1%p;
while(b)
{
if(b&1)res=res*a%p;
a=a*a%p;
b>>=1;
}
return res;
}
int phi(int x)
{
int res=x;
for(int i=2;i*i<=x;i++)
{
if(x%i==0)res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int a,b;
cin>>a>>b;
if(a!=1)cout<<qmi(a,b-1)*phi(a)%p<<endl;
else cout<<0<<endl;
return 0;
}