欧拉函数问题求解
作者:
comum
,
2024-04-14 23:51:08
,
所有人可见
,
阅读 5
欧拉函数
phi(1) = 0 ???????
可是gcd(1,1) = 1 由定义不是应该 phi(1) = 1 吗????
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
typedef long long LL;
int qMi(LL a, LL b) //快速幂 -> 指数转化为二进制,底数每次自倍增
{
LL res = 1;
while(b)
{
if(b & 1) res = res * a % mod;
a = a * a % mod; //自倍增 -> 指数:1、 2、 4、8、 ...
b >>= 1;
}
return res;
}
int main()
{
LL a, b;
cin >> a >> b;
if(a == 1) //a == 1的时候,没有区间,直接输出0
{
cout << 0;
return 0;
}
//计算phi(a)使得 -> a / pi 可以整出(a ^ b会溢出的嗷)
LL res = a, x = a;
for(int i = 2; i <= x / i; i++) //枚举可能的质因子 -> 最大到sqrt(x)
{
if(x % i == 0)
{
res = res / i * (i - 1) % mod;
while(x % i == 0)
x /= i;
}
}
if(x > 1) res = res / x * (x - 1) % mod;
cout << res * qMi(a, b - 1) % mod;
return 0;
}