互质数个数_(欧拉函数，快速幂)

原题链接：4968. 互质数的个数 - AcWing题库

题意：求 $1-a^b$ 中有有多少数是 $a^b$ 的互质数

思路

互质数数量——欧拉函数

概念

定义 $\varphi (n)$ 为欧拉函数 其等于 1~n当中与n互质的数的个数 公式 $\varphi (N)=N(1-\frac{1}{p_1})(1-\frac{1}{p_2})......\frac{1}{p_k}$ 其中 p 为质数

证明

利用 容斥原理 证明，将公式乘开可以看到： 1. 奇数$P_k$相减，偶数$p_k$相加，正是不考虑重叠部分，先减去再加回 2. 首先，每个数都可以拆成质因数p相乘，$\frac{N}{p}$ 意味着1~N中，p的倍数的个数，其余N都有p为约数，所以不是互质数，$N-\frac{N}{p}$ 就是去掉这些数，由于每个数都是p的相乘(或幂)，$\frac{N}{p}$ 可以表示N以内所有可能的数。 3. 容斥原理，先减去再加回可以算出剩余的数，即互质数的个数

Link to original

但是考虑到 $a^b$ 的表示虽然可以用快速幂求，但是取模后，其欧拉函数数值会与原来不同

发现$a^b$ 的质因数与 $a$ 完全一致，只是每个多个幂指数b 即 $a^b的欧拉函数=a^{b-1}\times a的欧拉函数$

快速幂求 $a^{b-1}$ 再求 a的欧拉函数

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
typedef long long LL;
 
const int mod = 998244353;
 
 
 
LL ans;
LL a, b;
 
int main()
{
    cin >> a >> b;
    
    //特判1，因为此题a取不到
    if(a == 1)
    {
        cout << 0 << endl;
        return 0;
    }
    
    LL t = a;
    ans = a;
    //cout << ans << endl;
    for(int i = 2; i <= a / i; i ++)
    {
        if(a % i == 0)
        {
            //找到素数
            ans = ans / i * (i - 1);
            while(a % i == 0)
            {
                a /= i;
            }
        }
    }
    //a大于根号a的那个数刚好是质数
    if(a > 1)
        ans = ans / a * (a - 1);
    
    //a的质因数就是a^b的质因数
    //a^b 的欧拉函数等于 a^b-1  * a的欧拉函数,为什么拆开a，是因为取模后求欧拉函数
    //不一定可以整除，数值不一定对
    
    //a的快速幂
    LL res = 1;
    b = b - 1;
    while(b)
    {
        if(b & 1) res = res * t % mod;
        b >>= 1;
        t = t * t % mod;
    }
    //cout << ans << endl;
    ans = res * ans % mod;
    
    cout << ans << endl;
    
    return 0;
}

这么简单的数学怎么会不懂呢