但能不能别没收我的爱？
Iniaugoty
·
·
题解
Upd on 2025/7/24：发现本题存在一个预处理严格线性、查询根号的做法。这篇题解原本的做法是一年半前写的，比较差，就丢剪贴板了。
爆标了但是不能够跑到最优解，怎么会是呢？
是基于这个或这个的进一步优化，看过的可以跳过前半部分。
注意到 P = 32465177 是质数，存在原根 g = 3，因此我们将原式对 g 取离散对数，并且做一个差分，于是只需求出
F(x, y) = \sum _ {i = 1} ^ x \sum _ {j = 1} ^ y \operatorname{lcm}(i, j) \ln (\operatorname{lcm}(i, j))
则 g ^ {F(r, r) - 2F(l - 1, r) + F(l - 1, l - 1)} \bmod P 即为答案。
进行一些套路性的转化和莫比乌斯反演，钦定 x \le y，
F(x, y) & = \sum _ {i = 1} ^ x \sum _ {j = 1} ^ y \frac {ij} {\gcd (i, j)} \ln \left( \frac {ij} {\gcd (i, j)} \right) \\
& = \sum _ {d = 1} ^ {x} \sum _ {i = 1} ^ {\lfloor \frac x d \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y d \rfloor} ijd \cdot \ln (ijd) [\gcd(i, j) = 1] \\
& = \sum _ {d = 1} ^ {x} \sum _ {e = 1} ^ {\lfloor \frac x d \rfloor} \sum _ {i = 1} ^ {\lfloor \frac x {de} \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y {de} \rfloor} ijde^2 \cdot \ln (ijde^2) \mu(e) \\
\end {aligned}
设 T = de 并枚举之，
F(x, y) = \sum _ {T = 1} ^ x T \sum _ {e \mid T} e \mu(e) \sum _ {i = 1} ^ {\lfloor \frac x T \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y T \rfloor} ij \cdot \ln (ijeT)
设 $f(n) = \sum _ {d \mid n} d \mu(d)$，$g(n) = \sum _ {d \mid n} d \mu(d) \ln d$，
设 $S(n) = \sum _ {i = 1} ^ n i \ln i$，$T(n) = \sum _ {i = 1} ^ n = \frac {n(n + 1)} 2$，
$$\sum _ {T = 1} ^ x T \sum _ {e \mid T} e\mu(e) \sum _ {i = 1} ^ {\lfloor \frac x T \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y T \rfloor} ij \ln i
= \sum _ {T = 1} ^ x T \cdot f(T) S(\lfloor \frac x T \rfloor)
T(\lfloor \frac y T \rfloor)$$
$$\sum _ {T = 1} ^ x T \sum _ {e \mid T} e\mu(e) \sum _ {i = 1} ^ {\lfloor \frac x T \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y T \rfloor} ij \ln T
= \sum _ {T = 1} ^ x T \cdot \ln T \cdot f(T) T(\lfloor \frac x T \rfloor) T(\lfloor \frac y T \rfloor)$$
$$\sum _ {T = 1} ^ x T \sum _ {e \mid T} e\mu(e) \sum _ {i = 1} ^ {\lfloor \frac x T \rfloor} \sum _ {j = 1} ^ {\lfloor \frac y T \rfloor} ij \ln e
= \sum _ {T = 1} ^ x T \cdot g(T) T(\lfloor \frac x T \rfloor) T(\lfloor \frac y T \rfloor)$$
不难发现，只需预处理出 $n \cdot f(n), n \cdot \ln n \cdot f(n), n \cdot g(n)$ 的前缀和及 $S(n), T(n)$，每次询问便容易利用整除分块做到 $\mathcal O(\sqrt n)$。
而本质上要求的只是 $\ln n, f(n), g(n)$。
$\mathcal O(P)$ 求出 $\ln n$ 是简单的，$g ^ 0, g ^ 1, g ^ 2, \dots, g ^ {P - 2}$ 恰好取遍 $1, 2, 3, \dots, P - 1$。
问题是 $f(n)$ 和 $g(n)$，类似做法的题解瓶颈亦在于此。
首先求 $f(n) = \sum _ {d \mid n} d \mu(d)$ 不难。其形如一个积性函数的 Dirichlet 前缀和，显然也是一个积性函数，因此我们考虑其在质数幂处的取值。
设 $p$ 为质数，$\alpha > 0$，则 $f(p ^ \alpha) = \sum _ {i = 0} ^ \alpha p ^ i \mu (p ^ i)$，由于有个 $\mu$，当仅 $i < 2$ 时才有非 $0$ 取值，故 $f(p ^ \alpha) = 1 - p$。
考虑 $n$ 被其最小质因子 $p$ 筛到，若 $p \mid \frac n p $，则 $f(n) = f(\frac n p)$，否则 $f(n) = (1 - p) f(\frac n p)$。
这样便做到了线性筛 $f(n)$。
但是 $g(n) = \sum _ {d \mid n} d \mu(d) \ln d$ 并不具有积性，只能高维前缀和做到 $\mathcal O(n \log \log n)$，对吗对吗？
不对不对不对！
**仅有无平方因子的 $d$ 才会产生贡献**。设 $n$ 的质因数分解为 $p_1 ^ {\alpha_1} p_2 ^ {\alpha_2} \dots p_k ^ {\alpha_k}$，则这意味着 $d \mid p_1 p_2 \dots p_k$，也就是说 $f(n) = f(p_1 p_2 \dots p_k)$。
考虑将 $n$ 的某个质因子 $p$ 拆掉，讨论 $p \mid d$ 和 $p \nmid d$ 两种情况并求和，
$$\begin {aligned}
g(n) & = \sum _ {d \mid n} d \mu (d) \ln d \\
& = \sum _ {d \mid \frac n p} d \mu (d) \ln d + (d \cdot p) \mu (d \cdot p) \ln (d \cdot p) \\
& = \sum _ {d \mid \frac n p} d \mu (d) \ln d - (d \cdot p) \mu (d) \ln d - (d \cdot p) \mu(d) \ln p \\
& = \sum _ {d \mid \frac n p} (1 - p) \cdot d \mu (d) \ln d - p \ln p \cdot d \mu (d) \\
& = \left( (1 - p) \sum _ {d \mid \frac n p} d \mu (d) \ln d \right) - \left( p \ln p \sum _ {d \mid \frac n p} d \mu (d) \right) \\
& = (1 - p) g(\frac n p) - p \ln p \cdot f(\frac n p)
\end {aligned}$$
这显然可以愉快地线性筛！考虑 $n$ 被其最小质因子 $p$ 筛到，若 $p \mid \frac n p$，则 $g(n) = g(\frac n p)$，否则利用上式。
**综上，我们使用 $\mathcal O(P + n + T \sqrt n)$ 的时间复杂度解决了本题**。
实现的时候，注意求的其实是指数上的值，对 $P - 1$ 取模，其他没什么要注意的。
```cpp
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 1e6 + 5;
const int P = 32465177;
const int M = P - 1, G = 3;
int qPow(int x, int y) {
int res = 1;
for (; y; x = 1ll * x * x % P, y >>= 1)
if (y & 1) res = 1ll * res * x % P;
return res;
}
int Add(int x, int y) { return x + y >= M ? x + y - M : x + y; }
int Sub(int x, int y) { return x - y < 0 ? x - y + M : x - y; }
int T, n;
int ln[N], f[N], g[N], pr[N], tot; bool vis[N];
int s[N], t[N], s1[N], s2[N], s3[N], s0[N];
void Init() {
for (int i = 0, j = 1; i <= P - 2; ++i) {
if (j <= n) ln[j] = i;
j = 1ll * j * G % P;
}
f[1] = 1, g[1] = 0;
for (int i = 2; i <= n; ++i) {
if (!vis[i])
pr[++tot] = i, f[i] = M + 1 - i,
g[i] = 1ll * (M - i) * ln[i] % M;
for (int j = 1; j <= tot && i * pr[j] <= n; ++j) {
int u = i * pr[j]; vis[u] = 1;
if (i % pr[j] == 0) { f[u] = f[i], g[u] = g[i]; break; }
else
f[u] = 1ll * (M + 1 - pr[j]) * f[i] % M,
g[u] = Sub(1ll * (M + 1 - pr[j]) * g[i] % M,
1ll * pr[j] * ln[pr[j]] % M * f[i] % M);
}
}
for (int i = 1; i <= n; ++i)
s[i] = Add(s[i - 1], 1ll * i * ln[i] % M),
t[i] = Add(t[i - 1], i),
s1[i] = Add(s1[i - 1], 1ll * i * f[i] % M),
s2[i] = Add(s2[i - 1], 1ll * i * ln[i] % M * f[i] % M),
s3[i] = Add(s3[i - 1], 1ll * i * g[i] % M);
for (int i = 1; i <= n; ++i)
s0[i] = Add(s2[i], s3[i]);
}
int F(int x, int y) {
if (!x || !y) return 0;
int res = 0;
for (int l = 1, r; l <= x; l = r + 1) {
r = min(x / (x / l), y / (y / l));
int u = 1ll * s[x / l] * t[y / l] % M;
int v = 1ll * t[x / l] * s[y / l] % M;
res = Add(res, 1ll * Sub(s1[r], s1[l - 1]) * Add(u, v) % M);
}
for (int l = 1, r; l <= x; l = r + 1) {
r = min(x / (x / l), y / (y / l));
int u = Sub(s0[r], s0[l - 1]);
int v = 1ll * t[x / l] * t[y / l] % M;
res = Add(res, 1ll * u * v % M);
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T >> n, Init();
while (T--) {
int l, r; cin >> l >> r;
int tmp = Add(F(r, r), F(l - 1, l - 1));
tmp = Sub(tmp, 2ll * F(l - 1, r) % M);
cout << qPow(G, tmp) << "\n";
}
return 0;
}
```