条件の言い換え

「\(a \bmod b = c\)」という条件があることから，条件を満たす整数の組は \((a,b,a \bmod b)\) の形で表せます． そこで，\((a,b,c)\) に関する条件を \((a,b)\) に関する条件に言い換えて，それを満たす \((a,b)\) を数え上げることを考えます．

\(a < b\) の場合は，\(c = a \bmod b = a\) となるので，「\(a,b,c\) が相異なる」という条件に必ず反します． 逆に，\(a > b\) の場合は，\(c = a \bmod b < b\) となるので，「\(a,b,c\) が相異なる」という条件は必ず満たされます．

また，\(c = a \bmod b\) が正であることは，\(a\) が \(b\) の倍数でないことで言い換えられます．

したがって，以下を満たす整数の組 \((a,b)\) の個数を数えればよいです．

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

数え上げ

\(b \in \{1, \dots, N\}\) を特定の値に固定したとき，条件を満たすような \(a\) の個数を \(f(N, b)\) とおきます．

\(b+1\) 以上 \(N\) 以下の整数は \(N-b\) 個あり，そのうち \(b\) の倍数は \(\lfloor \frac{N}{b} \rfloor - 1\) 個あるので，\(f(N,b) = (N - b) - (\lfloor \frac{N}{b} \rfloor - 1)\) とわかります．

よって，求める値は \(b = 1, \dots, N\) に対する \(f(N,b)\) の総和，つまり

\[\sum_{b = 1}^{N} \left(N - b + 1 - \left\lfloor \frac{N}{b} \right\rfloor\right )\]

と表せます．

高速化

\(N \leq 10^{12}\) という制約下において，上の式を愚直に計算すると間に合わないでしょう．

上の式を，以下のように \(2\) つの項に分けて考えます．

\[\sum_{b = 1}^{N} \left(N - b + 1 \right) - \sum_{b=1}^N \left\lfloor \frac{N}{b} \right\rfloor\]

第 1 項

第 \(1\) 項は，開いてみると \(N + (N-1) + \dots + 2 + 1\) という形をしています．これは等差数列の和であり，その値は \(\displaystyle\frac{N(N+1)}{2}\) と簡潔に書けます．

第 2 項

第 \(2\) 項について考えます．

\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor\) の値を観察すると，\(b > \sqrt{N}\) のときは \(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor < \sqrt{N}\) であることから，\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor\) の値は高々 \(2 \sqrt{N}\) 種類の値しかとらないことがわかります．

そこで，以下のように \(2\) 段階に分けて計算することを考えます．

• \(k = 1, \cdots, \lfloor \sqrt{N} \rfloor\) に対しては，\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor = k\) であるような \(b\) の範囲を求め(方法は後述)，それらの \(b\) についてまとめて和を計算する．
• 上でカバーしなかった \(b\) については，個別に \(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor\) を計算して足し合わせる．

前半の段階でカバーされない \(b\) は，\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor \geq \displaystyle\left\lfloor \sqrt{N} \right\rfloor + 1\) を満たすことから，

\[ \frac{N}{b} \geq \displaystyle\left\lfloor \frac{N}{b} \right\rfloor \geq \displaystyle\left\lfloor \sqrt{N} \right\rfloor + 1 > \sqrt{N} \]

より \(b < \sqrt{N}\) を満たします．よって，後半の段階で扱われる \(b\) は \(\lfloor \sqrt{N} \rfloor\) 以下のもののみとわかり，前半・後半ともに \(O(\sqrt{N})\) 時間で計算できます．

\(N\) の値が大きいので，計算途中でオーバーフローする危険性に十分注意して実装する必要があります．また，今回の問題では必要ありませんが，多倍長整数で非常に大きな数値をそのまま持つと四則演算程度の計算でも重くなるので，適宜 mod をとりながら計算する必要があります．

\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor = k\) を満たす整数 \(b\) の範囲

\(\displaystyle\left\lfloor \frac{N}{b} \right\rfloor = k\) を満たす整数 \(b\) の範囲は，式変形によって

\[ \begin{aligned} \displaystyle\left\lfloor \frac{N}{b} \right\rfloor = k &\Longleftrightarrow k \leq \frac{N}{b} < k+1 \\ &\Longleftrightarrow \frac{N}{k+1} < b \leq \frac{N}{k} \\ &\Longleftrightarrow \left\lfloor\frac{N}{k+1}\right\rfloor + 1 \leq b \leq \left\lfloor\frac{N}{k}\right\rfloor \end{aligned} \]

と求まります．

実装例 (C++)

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
using std::string;
using std::to_string;
using std::pair;
using std::make_pair;
using std::vector;
using std::min;
using std::max;
using std::array;

#include <atcoder/all>
using mint = atcoder::modint998244353;

typedef long long int ll;

ll n;

void solve () {
	mint fsum = 0; // will be the sum of floor(n/b) (1 <= b <= n)

	ll prevk = -1;
	ll idx = 1;
	while (true) {
		// floor(n/k) == idx
		// <=> idx <= n/k < idx+1
		// <=> n/(idx+1) < k <= n/idx
		// <=> floor(n/(idx+1)) + 1 <= k <= floor(n/idx)

		ll l = n / (idx+1) + 1;
		ll r = n / idx;

		if (l <= r) fsum += (mint)(r-l+1) * (mint)idx;

		prevk = l;
		if (prevk <= n / prevk) break;

		idx++;
	}
	while (--prevk >= 1) {
		fsum += (mint)(n / prevk);
	}

	mint ans = 0; // the sum of (n-b+1) - floor(n/b)
	ans += (mint)n * (mint)(n+1) / (mint)2;
	ans -= fsum;

	cout << ans.val() << "\n";
	return;
}

int main (void) {
	std::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n;

	solve();

	return 0;
}