题解 | #Calculation#

赛后补题时看其他神仙队伍的代码瞎琢磨的，大概率是绕了弯路，欢迎指正！

$\begin{align*} &\sum_{i=1}^{n} \sum_{j=1}^{n}\sum_{k=1}^{n} ({\lambda(i) \times \lambda(j) \times [i\mid j \ \text{and} \ j\mid k]}) \\ =&\sum_{i=1}^{n} \sum_{j=1}^{n}\sum_{k=1}^{n} ({\lambda(i) \times \lambda(j) \times [i\mid j] \times [j\mid k]}) \\ =&\sum_{i=1}^{n} \sum_{j=1}^{n} (\lambda(i) \times \lambda(j) \times [i\mid j] \times \sum_{k=1}^{n} ([j\mid k])) \\ =&\sum_{i=1}^{n} \sum_{j=1}^{n} (\lambda(i) \times \lambda(j) \times [i\mid j] \times \lfloor \frac{n}{j} \rfloor) \\ =&\sum_{j=1}^{n} ( \lfloor \frac{n}{j} \rfloor \times \sum_{i=1}^{j} (\lambda(i) \times \lambda(j) \times [i\mid j])) \\ \end{align*}$

不妨设：

$\begin{align*} j&=p_1^{a_1} \times p_2^{a_2} \times … \times p_k^{a_k} \\ i&=p_1^{a_1'} \times p_2^{a_2'} \times … \times p_k^{a_k'} \end{align*}$

则：

$\begin{align*} \lambda(i) \times \lambda(j) =(-1)^{a_1+a_2+...+a_k+a_1'+a_2'+...+a_k'} \end{align*}$

注意到当 $j$ 不是完全平方数时， $a_1,a_2,...a_k$ 至少有一个是奇数，我们不妨假设 $a_k$ 是奇数。当 $i \mid j$ 时，有 $a_t' \leq a_t \ (1 \leq t \leq k)$ ，所以 $a_k'$ 有 $0,1,2,3,...,a_k-1,a_k$ 共 $a_k+1$ 种可能的情况，即偶数种情况。无论 $a_1+a_2+...+a_k+a_1'+a_2'+...+a_{k-1}'$ 的奇偶性如何，由于 $a_k'$ 是奇数的情况数跟 $a_k'$ 是偶数的情况数相同，所以 $a_1+a_2+...+a_k+a_1'+a_2'+...+a_k'$ 值为奇数的情况数也一定跟值为偶数的情况数相同，则 $\sum_{i=1}^{j} (\lambda(i) \times \lambda(j) \times [i\mid j])=0$ 。

当 $j$ 是完全平方数时， $a_1,a_2,...a_k$ 都是偶数，当 $i \mid j$ 时，对于每个 $a_t' \ (1 \leq t \leq k)$ 都有 $0,1,2,3,...,a_t$ 一共是奇数种可能的情况。当 $a_k'< a_k$ 时情况同上。当 $a_k'= a_k$ 时由于 $a_k'$ 为偶数，则转为讨论 $a_1+a_2+...+a_k+a_1'+a_2'+...+a_{k-1}'$ 的奇偶性，以此类推，最终转为讨论 $a_1+a_2+...+a_k+a_1'$ 的奇偶性，显然 $a_1'$ 是偶数的情况比 $a_1'$ 是奇数的情况多一种，所以 $a_1+a_2+...+a_k+a_1'+a_2'+...+a_k'$ 值为偶数的情况比值为奇数的情况多一种，则 $\sum_{i=1}^{j} (\lambda(i) \times \lambda(j) \times [i\mid j])=1$ 。

接下来可以使用整除分块，即枚举 $\lfloor \frac{n}{j} \rfloor$ 的值，计算此时 $j$ 的值应该落在哪个区间，假设是 $[l,r]$ ，只需讨论 $[l,r]$ 中有多少完全平方数即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;

ll S(ll x)
{
    return sqrt(x);
}

ll n, s;

int main()
{
    cin >> n;
    for (ll l = 1, r; l <= n; l = r + 1)
    {
        r = n / (n / l);
        s = (s + (n / l) * (S(r) - S(l - 1))) % MOD;
    }
    cout << s << '\n';
}