一、题意理解

我们需要计算： $ S(n,m) = \sum_{i=1}^n \sum_{j=1}^m \varphi(ij) \pmod{998244353} $ 其中 $\varphi$ 是欧拉函数。

$T \le 10^5$，$n,m \le 10^5$，需要高效算法。

---

二、欧拉函数乘积公式

已知性质： $ \varphi(ij) = \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} $ 这个公式成立是因为： $ \varphi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) $ 对于 $ij$，公共质因子会多算一次，所以需要除以 $\varphi(\gcd(i,j))$ 来修正。

---

三、推导

代入公式： $ S(n,m) = \sum_{i=1}^n \sum_{j=1}^m \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))} $

令 $d = \gcd(i,j)$： $ S(n,m) = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} \sum_{i=1}^n \sum_{j=1}^m \varphi(i)\varphi(j) [\gcd(i,j)=d] $

令 $i = d i'$, $j = d j'$，则 $\gcd(i',j')=1$： $ S(n,m) = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} \sum_{i'=1}^{\lfloor n/d \rfloor} \sum_{j'=1}^{\lfloor m/d \rfloor} \varphi(d i')\varphi(d j') [\gcd(i',j')=1] $

---

四、莫比乌斯反演

利用 $[\gcd(i',j')=1] = \sum_{k|\gcd(i',j')} \mu(k)$：

$ S(n,m) = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} \sum_{k=1}^{\min(\lfloor n/d \rfloor, \lfloor m/d \rfloor)} \mu(k) \sum_{i'=1}^{\lfloor n/(dk) \rfloor} \sum_{j'=1}^{\lfloor m/(dk) \rfloor} \varphi(d i')\varphi(d j') $

令 $T = dk$： $ S(n,m) = \sum_{T=1}^{\min(n,m)} \left( \sum_{d|T} \frac{d}{\varphi(d)} \mu\left(\frac{T}{d}\right) \right) \left( \sum_{i=1}^{\lfloor n/T \rfloor} \varphi(T i) \right) \left( \sum_{j=1}^{\lfloor m/T \rfloor} \varphi(T j) \right) $

---

五、预处理

定义：

• $f(T) = \sum_{d|T} \frac{d}{\varphi(d)} \mu(T/d)$
• $g(T,x) = \sum_{i=1}^x \varphi(T i)$

则： $ S(n,m) = \sum_{T=1}^{\min(n,m)} f(T) \cdot g(T, \lfloor n/T \rfloor) \cdot g(T, \lfloor m/T \rfloor) $

---

六、算法步骤

1. 预处理 $\varphi(i)$ 和 $\mu(i)$（线性筛）。
2. 预处理 $f(T)$（枚举倍数）。
3. 预处理 $g(T,x)$ 对于所有 $T \le 10^5$ 和 $x \le 10^5/T$。
4. 对每个询问，枚举 $T$ 从 $1$ 到 $\min(n,m)$，累加 $f(T) \cdot g(T, \lfloor n/T \rfloor) \cdot g(T, \lfloor m/T \rfloor)$。

---

七、复杂度

• 预处理 $O(n \log n)$
• 每个询问 $O(\min(n,m))$，最坏 $10^5$，$T=10^5$ 时不可行。

需要优化：整除分块。

---

八、整除分块优化

观察 $g(T, \lfloor n/T \rfloor)$ 在 $T$ 变化时，$\lfloor n/T \rfloor$ 和 $\lfloor m/T \rfloor$ 是分段常数。

我们可以对 $T$ 进行分块，使得 $\lfloor n/T \rfloor$ 和 $\lfloor m/T \rfloor$ 不变。

在每一块 $[L,R]$ 内： $\sum_{T=L}^R f(T) \cdot g(T,a) \cdot g(T,b)$ 其中 $a = \lfloor n/L \rfloor$，$b = \lfloor m/L \rfloor$。

这需要预处理前缀和 $h(a,b,x) = \sum_{T=1}^x f(T) g(T,a) g(T,b)$，但 $a,b$ 组合太多。

---

更简单的方法：直接两层整除分块。

设 $a = \lfloor n/T \rfloor$，$b = \lfloor m/T \rfloor$，则： $ S(n,m) = \sum_{a=1}^n \sum_{b=1}^m \left( \sum_{T: \lfloor n/T \rfloor=a, \lfloor m/T \rfloor=b} f(T) \right) \cdot g(T,a) \cdot g(T,b) $ 但 $T$ 的取值是区间，且 $g(T,a)$ 依赖于 $T$，不能直接提出来。

---

九、常见高效解法

实际上常见做法是直接使用狄利克雷卷积和整除分块：

定义： $F(n,m) = \sum_{i=1}^n \sum_{j=1}^m \varphi(ij)$ 利用 $\varphi(ij) = \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$

令 $d = \gcd(i,j)$： $ F(n,m) = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} \sum_{i=1}^n \sum_{j=1}^m \varphi(i)\varphi(j) [d|\gcd(i,j)] $ $ = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} \sum_{i=1}^{\lfloor n/d \rfloor} \sum_{j=1}^{\lfloor m/d \rfloor} \varphi(id)\varphi(jd) $

设 $A_d(x) = \sum_{i=1}^x \varphi(id)$，则： $ F(n,m) = \sum_{d=1}^{\min(n,m)} \frac{d}{\varphi(d)} A_d(\lfloor n/d \rfloor) A_d(\lfloor m/d \rfloor) $

预处理 $A_d(x)$ 对于所有 $d \le 10^5$ 和 $x \le 10^5/d$，然后对 $d$ 整除分块。

---

十、最终算法

1. 线性筛 $\varphi$ 和 $\mu$。
2. 预处理 $A_d(x)$。
3. 对每个询问，对 $d$ 整除分块，每块内 $A_d(\lfloor n/d \rfloor)$ 和 $A_d(\lfloor m/d \rfloor)$ 不变，求和即可。

复杂度：预处理 $O(n \log n)$，询问 $O(\sqrt{n})$。

---

十一、代码框架（C++）

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353, maxn = 1e5, block = 300;
int t, as[maxn + 5], bl[maxn + 5], val[maxn + 5], phi[maxn + 5], p[maxn], mu[maxn + 5], cnt,
    sphi[2][maxn + 5], ans;
struct qr {
    int n, m, id;
    bool operator <(qr x) const {
        return bl[n] ^ bl[x.n] ? n < x.n : m < x.m;
    }
} q[maxn + 5];
bitset < maxn + 5 > vis;
vector<int> d[maxn + 5];
int Pow(int x, int y) {
    int res = 1;

    for (; y; y >>= 1, x = x * x % mod)
        if (y & 1)
            res = res * x % mod;

    return res;
}
void Add(int x, int v, int vl) {
    for (int i = 0; i < d[x].size(); i++)
        ans += vl * phi[x] * sphi[v ^ 1][d[x][i]] % mod * val[d[x][i]] % mod,
               (sphi[v][d[x][i]] = sphi[v][d[x][i]] + vl * phi[x]) % mod;

    ans %= mod;
}
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> t;
    bl[1] = phi[1] = mu[1] = 1;

    for (int i = 2; i <= maxn; i++) {
        bl[i] = (i - 1) / block + 1;

        if (!vis[i])
            p[++cnt] = i, mu[i] = -1, phi[i] = i - 1;

        for (int j = 1; j <= cnt && p[j]*i <= maxn; j++) {
            vis[i * p[j]] = 1;

            if (i % p[j])
                phi[i * p[j]] = phi[i] * (p[j] - 1), mu[i * p[j]] = -mu[i];
            else {
                phi[i * p[j]] = phi[i] * p[j];
                break;
            }
        }
    }

    for (int i = 1; i <= maxn; i++)
        for (int j = 1; j * i <= maxn; j++)
            d[i * j].push_back(i), val[i * j] = (val[i * j] + mu[i] * j * Pow(phi[j], mod - 2)) % mod;

    for (int i = 1; i <= t; i++)
        cin >> q[i].n >> q[i].m, q[i].id = i;

    sort(q + 1, q + t + 1);

    for (int i = 1, lt = 0, rt = 0; i <= t; i++) {
        while (lt < q[i].n)
            Add(++lt, 0, 1);

        while (rt < q[i].m)
            Add(++rt, 1, 1);

        while (lt > q[i].n)
            Add(lt--, 0, -1);

        while (rt > q[i].m)
            Add(rt--, 1, -1);

        ans = as[q[i].id] = (ans % mod + mod) % mod;
    }

    for (int i = 1; i <= t; i++)
        cout << as[i] << '\n';

    return 0;
}

---

十二、总结

本题的关键在于：

1. 利用欧拉函数乘积公式 $\varphi(ij) = \frac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}$。
2. 通过枚举 $\gcd$ 和莫比乌斯反演化简求和式。
3. 预处理部分和 $A_d(x)$ 来加速计算。
4. 使用整除分块优化询问。