AcWing 4968. 互质数的个数
原题链接
中等
作者:
너
,
2024-04-05 19:38:32
,
所有人可见
,
阅读 3
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int mod = 998244353;
typedef long long LL;
vector<pair<int, int> > indx;
LL a, b, ans = 1;
//分解质因数
void divide(int x)
{
for(int i = 2; i * i <= x; i ++ )
{
int cnt = 0;
while(x % i == 0)
{
cnt ++;
x /= i;
}
if(cnt > 0)
indx.push_back({i, cnt});
}
if(x > 1) indx.push_back({x, 1});
}
//快速幂模板
LL qmi(LL a, LL b, LL p)
{
LL res = 1;
while(b)
{
if(b & 1)
{
res = res * a % p;
}
a = a * a % p;
b >>= 1;
}
return res;
}
int main()
{
cin >> a >> b;
//对a分解质因数 a=1特判
divide(a);
ans = a;
for(auto t : indx)
{
int x = t.first, y = t.second;
//cout << x << ' ' << y << endl;
ans = ans / x * (x - 1); //欧拉函数
}
//cout << ans;
if(a == 1) ans = 0; //特判a=1
//欧拉函数前面是一堆分数,一堆分数要乘上一个数才能不丢失精度
//所以要在b个a中拿走一个,乘给这一堆分数,才能是一个整数
cout << ans * qmi(a, b - 1, mod) % mod << endl;
return 0;
}