题目链接：https://ac.nowcoder.com/acm/contest/11254/E
题目大意：(sum_{i=1}^{n}sum_{j=1}^{jleqslant i} left [ ij+1mid i^{2} + j^{2} ight ])
题目思路：
(xy+1mid x^{2} + y^{2})即为(x^{2} + y^{2} = kleft ( xy+1
ight ))将x看为常数，得(y^{2}-kxy+x^{2}-k=0)，根据韦达定理:
若有一组(left ( x,y ight ))满足条件，则(left ( x,kx-y ight ))也满足条件，设(ygeqslant x)，容易得到(kx-y leqslant y)。我们可以通过递降推出其他解，即构造(left ( x',y' ight ))，使(x' = kx - y)，(y' = x)，此时仍然满足(x^{2} + y^{2} = kleft ( xy+1 ight ))，继续将(x')看成常数向下递降，即((x,y) ightarrow (kx-y,x))
之前我直接构造(left ( x',y' ight ))，使(x' = x,y' = kx - y)，然后我发现继递降出来的是(kx - y' = y)，这不和没构造一样吗 （bushi
而且这样递降下来的(y'geqslant 0)，若将(y'< 0)代入(x^{2} + y^{2} = kleft ( xy+1 ight ))，得到正数=负数，显然(y'geqslant 0)，将(y = 0)代入得(k=x^{2})，通过往回递增得
即((x',y')
ightarrow (y',x^{2}y'- x') = (x,y))
即((x,x^{3})
ightarrow (x^{3},x^{5}-x)
ightarrow (x^{5}-x,x^{7}-2x^{3})
ightarrow ……)
然后枚举x，二分查找即可
水群时看见这个好像叫韦达跳跃
想了解的更多可以看看OEIS关于这个定理的解释
AC代码：
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <string>
#include <stack>
#include <deque>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef __int128 int128;
typedef pair<int, int> PII;
typedef pair<double, int> PDI;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;
const int N = 1e7 + 10, M = 1e6 + 30;
const int base = 1e9;
const int P = 131;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double PI = acos(-1.0);
int a[N];
vector<int128> vec;
void inif()
{
vec.push_back(1);
for (int128 k = 2; k <= 1e6; ++k)
{
int128 a = k, b = k * k * k, c;
while (1)
{
if (b > 1e18)
break;
vec.push_back(b);
c = k * k * b - a;
a = b, b = c;
}
}
sort(vec.begin(), vec.end());
}
int main()
{
inif();
int T;
scanf("%d", &T);
while (T--)
{
ll x;
scanf("%lld", &x);
int128 n = x;
int p = lower_bound(vec.begin(), vec.end(), n) - vec.begin();
if (vec[p] > n)
--p;
printf("%d
", p + 1);
}
return 0;
}