[ARC125B] Squares 题解

标签：std Squares end 题解 valueType le ARC125B aligned

题意

给定正整数 \(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;
}

标签：std,Squares,end,题解,valueType,le,ARC125B,aligned
From： https://www.cnblogs.com/User-Unauthorized/p/solution-ARC125B.html