🌟快速幂、欧拉函数
🍎解题思路
$1.$题目意思是让我们求解$\phi(a^b)$,即$a^b$的欧拉函数
$2.$因为$\phi(a^b) = a^b \times (1 - 1/p_1) \times (1 - 1/p_2) … (1 - 1/p_k)$,由算术基本定理,我们发现,a的质因数是$p_1^{\alpha1}, p_2^{\alpha2}, p_3^{\alpha3}…$的话,$a^b$的质因数不过是多了$b$的乘方,即$p_1^{\alpha1 \times b}, p_2^{\alpha2 \times b}, p_3^{\alpha3 \times b}…$,即底数的质因子不会因为乘方而改变
,依旧是原先的质因子。
3.因此,$\phi(a^b) = a^b \times (1 - 1/p_1) \times (1 - 1/p_2) … (1 - 1/p_k)$
就可以转化为👇
$\phi(a^b) = a^{b - 1} \times a \times (1 - 1/p_1) \times (1 - 1/p_2) … (1 - 1/p_k) = a^{b - 1} \times \phi(a)$
$4.$利用快速幂求解$a^{b - 1}$ ,欧拉函数公式求解$\phi(a)$,最后相乘取模之后就是$ans$
🍭技巧
$1.$如果质因子相同,那么欧拉函数有$\phi(a^b) = a^{b-1} \times \phi(a)$
$2.$快速幂利用指数二进制,底数自倍增,综合推进幂的结算,主要应用是:幂运算溢出可以在过程中取模、求逆元
🍇时间复杂度
$O(\sqrt{A})$
#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;
}
佬太牛了,思路真的很好