题意
给定正整数 \(N\)，求满足如下条件的正整数对 \((x, y)\) 的数量：
-
\(1 \le x, y \le N\)
-
\(x^2 - y\) 为完全平方数（\(0\) 也是完全平方数）
（\(1 \le N \le 10^{12}\)）。
题解
因为 \(x^2 - y\) 为完全平方数，设其为 \(z^2\)，那么有
\[\begin{aligned}
x^2 - y = z^2 \\
\end{aligned}\]
设 \(b = x - z\)，那么有
\[\begin{aligned}
(z + b)^2 - y &= z^2 \\
y &= 2bz + b^2
\end{aligned}\]
考虑到 \(2bz + b^2 = y \le N \Rightarrow b^2 \le N\)，因此 \(b\) 的取值个数是 \(\mathcal{O}(\sqrt{N})\) 级别的，所以可以枚举 \(b\) 的取值，接下来快速计算合法的 \(z\) 的个数，进而统计数对个数，那么有
\[\begin{aligned}
y &= 2bz + b^2 \Leftrightarrow z \le \dfrac{N - b^2}{2b}
\end{aligned}\]
有因为 \(x = z + b\)，所以有
\[x \le N \Leftrightarrow z \le N - b
\]
所以有
\[0 \le z \le \min\left\{\dfrac{N - b^2}{2b}, N - b\right\}
\]
故在钦定 \(b\) 的情况下可以快速计算合法的 \(z\) 的取值，总复杂度 \(\mathcal{O}(\sqrt{N})\)。
Code
#include <bits/stdc++.h>
typedef long long valueType;
constexpr valueType MOD = 998244353;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
valueType N;
std::cin >> N;
valueType ans = 0;
for (valueType i = 1; i * i <= N; ++i) {
ans += (std::min((N - i * i) / (2 * i), N - i) + 1) % MOD;
ans %= MOD;
}
std::cout << ans << std::endl;
return 0;
}