以下を満たす整数の組 \((a, b)\) の個数を数えれば良いです。

• \(2 \leq b < a \leq N\)
• \(a\) は \(b\) の倍数でない

よって、

• \(X\) : \(2 \leq b < a \leq N\)　を満たす \((a, b)\) の個数
• \(Y\) : \(2 \leq b < a \leq N\) かつ \(b\) が \(a\) を割り切るような \((a, b)\) の個数

としたとき答えは \(X - Y\) です。

\(X\) は \(2 \ldots N\) から相異なる整数を \(2\) つ選ぶ場合の数に等しいので \(X = _{N-1}C_2\) となります。

\(Y\) を計算することを考えます。 \(Y\) は以下を満たす整数の組 \((a, b, k)\) の個数に等しいです。

• \(a = b \cdot k\)
• \(a \leq N\)
• \(2 \leq b, k\)

ここで、これらの条件について \(b\) と \(k\) に対称性があることがわかります。厳密に言うと、 \((a, b, k) = (p, q, r)\) が条件を満たすなら \(q\) と \(r\) を入れ替えた \((a, b, k) = (p, r, q)\) も条件を満たします。

よって、上記の条件を満たす \((a, b, k)\) のうち \(b < k\) を満たすものの個数を \(2\) 倍し、それに \(b = k\) を満たすものの個数を足せば \(Y\) が求まります。これは、 \(b = 2 \ldots \lfloor \sqrt N \rfloor\) についてそれぞれ対応する \(k\) の個数を計算することで \(O(\sqrt N)\) 時間で計算できます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#include <atcoder/modint>
using mint = atcoder::modint998244353;

int main() {
    ll N;
    cin >> N;
    mint ans = (mint) (N - 1) * (N - 2) / 2;
    for (ll b = 2; b * b <= N; ++b) {
        ans -= (N / b - b) * 2 + 1;
    }
    cout << ans.val() << endl;
}