给你一个整数N，求满足以下条件的整数对$(x,y)$的个数对 998244353取模的结果

• $x,y \in [1,N]$
• $x^2-y\:$是一个平方数

对于任意一个平方数$x^2$,它与右边的平方数的距离为：

与$(x+1)^2$的距离为$(x+1)^2-x^2=2x+1$

与$(x+2)^2$的距离为$(x+2)^2-x^2=4x+4$

与$(x+3)^2$的距离为$(x+3)^2-x^2=6x+9$

与$(x+n)^2$的距离为$(x+n)^2-x^2=2nx+n^2$

显然，距离都必须小于等于$N$

那么对于x，给它最长为N的扩展长度，它能扩展多少个平方数？

设$x$能扩展的平方数个数为$n$​

$(x+n)^2-x^2\leq N$

解得: $n \leq \sqrt{N + x^2} - x$

所以对于每个$x$,它对答案的贡献是$\sqrt{N+x^2}-x$

得到这样的函数：

$f(x)=\sqrt{N+x^2}-x$

可以发现，每一个$x$对答案的贡献可能相同，为了减少枚举次数，可以将对答案贡献相同的$x$，缩成一个集合，直接加到答案里面。

例如$[x,x+t]$之间的数，往右扩展$N$的距离，能碰到的平方数个数都为$cnt$

那么，答案 $+\:t\times cnt$ 即可.

而这个区间怎么获得？

我们不妨设$i$，表示每个$x$对答案的贡献。

可以得到式子：$\sqrt{N+x^2}-x=i$

整理得：$x = \frac{(N-i^2)}{2i}$

这个$x$是对答案的贡献为$i$的区间下限。

由此可以求出，对答案贡献为$i-1$的区间的上限是 $x+1$

同理可以求出，对答案贡献为$i$的区间的上限是 $\frac{N-(i+1)^2}{2(i+1)}+1$

也就是当贡献为$i+1$的时候，区间的下界+1

所以，我们可以设$ans[i]$为 对答案贡献为i的区间的下限$ans[i]$​

那么对每个贡献$i$,我们给答案加上:$(ans[i] - (ans[i+1] + 1) + 1) * i$

可以证明的是，$i\leq \sqrt{N}$

所以时间复杂度为 $O(\sqrt{N})$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define INF 1e18
const int mod =998244353;
void slove(){
    int n;
    cin >> n;
    int all = sqrt(n);
    vector<int> ans(all + 10);
    for (int i = all; i >= 1; i--) {
        int x = (n - i * i) / (2 * i);
        int cnt = sqrt(n + x * x) - x;
        ans[i] = x;
    }
    ans[0] = ans[1] + 1; 
    int sum = 0;
    for (int i = 1; i <= all - 1; i++) {
        sum += (ans[i] - ans[i + 1]) * i % mod;
        sum %= mod;
    }
    //把i = all的情况单独拿出来
    sum = (sum % mod + (ans[all] + 1) * all % mod ) %mod;
    cout << sum << '\n';
}

signed main(){
    slove();
}