Loading... [Link](https://atcoder.jp/contests/arc125/tasks/arc125_b) ## Description 要求: $x^2 - y = z^2$, 满足 $1 \leq x, y \leq N, N \leq 10^{12}$ ## Sol 移项可得:$x^2 - z^2 = y$ ,利用平法差公式:$(x+z)(x-z) = y$ 令 $p = (x+z), q = (x-z)$,因为 $x, y, z \in Z$,所以 $p \geq q$,现在要求 $pq = y$,可以枚举 $q$,然后 $O(1)$ 计算合法的 $p$ 的个数。 注意范围:$q \leq p \leq \frac{N}{q}, p \equiv q \mod {2}$ ## Code ```cpp #include <bits/stdc++.h> #define int long long using namespace std; signed main() { int n, ans = 0; cin >> n; const int mod = 998244353; for (int i = 1, l, r; i * i <= n; ++ i) { l = min(i, n / i), r = max(i, n / i); ans = (ans + ((r - l) / 2ll + 1) % mod) % mod; } printf("%lld\n", ans); return 0; } ``` 最后修改:2021 年 10 月 30 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 如果觉得我的文章对你有用,请随意赞赏