2024寒假每日一题全部题解传送门>>

首先得知道求$1$~$N$内与$N$互质（最大公约数为1）的个数就等价于求$N$的欧拉函数。

由算术基本定理，假设$N$可以分解质因数为$N={p_1}^{a_1}{p_2}^{a_2}…{p_m}^{a_m}$。
则$N$的欧拉函数为：$\phi(N)=N\times\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times…\times\frac{p_m-1}{p_m}$。

由上述公式知：欧拉函数只与质因数相关，而$a^b$又是由$b$个$a$相乘得到的，故$a$的质因数即为$a^b$的质因数。

由题可知，要求$\phi(N)\%MOD$，即求$N\%MOD\times(\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times…\times\frac{p_m-1}{p_m})\%MOD$。

对于$N\%MOD$可以通过快速幂来求，而$(\frac{p_1-1}{p_1}\times\frac{p_2-1}{p_2}\times…\times\frac{p_m-1}{p_m})\%MOD$可以将$a$分解质因数来求。简单来说，就是两大模板。

注意：在分解质因数对分式进行取模时$\frac{a}{b}\%MOD \neq \frac{a\%MOD}{b}$，不可与乘法取模混为一谈。在对分式取模的时候，通常转化为分子乘以分母的逆元。
1. 当$n$为质数时，可以用快速幂求逆元：
$a/b\equiv a*x \pmod n$
两边同乘b可得 $a \equiv a * b * x \pmod n$
即 $1 \equiv b * x \pmod n$
同 $b * x \equiv 1 \pmod n$
由费马小定理可知，当$n$为质数时
$b^{n-1} \equiv 1 \pmod n$
拆一个$b$出来可得 $b * b ^ {n - 2} \equiv 1 \pmod n$
故当$n$为质数时，$b$的乘法逆元 $x = b ^ {n - 2}$
2. 当$n$不是质数时，可以用扩展欧几里得算法求逆元：
$a$有逆元的充要条件是$a$与$p$互质，所以$gcd(a, p) = 1$
假设$a$的逆元为$x$，那么有$a * x \equiv 1 \pmod p$
等价：$ax + py = 1$

注意到模数$998244353$恰巧是一个质数，所以本题可以直接用快速幂来求逆元。同时题目需要求得是$1$~$N-1$内质数的个数，正常情况下与$N$互质的数不会包含本身，但对于$1$来说与它互质的数只有它本身，所以对于$1$需要特判一下!另外，由$a$有逆元的充要条件：$a$必须与模数互质。模数$998244353$为质数，只要$a$不是模数的倍数即可，而$a$的取值范围是$10^9$，故可能与模数相等，此时两者不再互质，不满足逆元的条件，所以这种情况无法用逆元来求，手算加特判即可！

C++代码：

#include<iostream>
using namespace std;
typedef long long LL;
const int MOD = 998244353;
LL a, b;

int qmi(LL a, LL b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = res * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }

    return res;
}

int divide(LL a, LL b)
{
    return a * qmi(b, MOD - 2) % MOD;
}

int main()
{
    scanf("%lld%lld", &a, &b);

    LL res = qmi(a, b), t = a;
    for(int i = 2; i <= t / i; i ++)
    {
        if(t % i == 0) res = res * divide(i - 1, i) % MOD;
        while(t % i == 0) t /= i;
    }

    if(t != 1) res = res * divide(t - 1, t) % MOD;

    if(a == 1) res = 0;
    if(a == 998244353 && b == 1) res = 998244352;

    printf("%d", res);
    return 0;
}