题解 CF1781D

· · 题解

abc1057510554 老师说，搞这种数论题，就可以在 CF 上 number theory 板刷一个 1300-1900 就可以了。

然后发现连 1800 的题都做不出来，我可以退役力 QAQ

观察到 n 很小，也就是说我们甚至可以用 O(n^4) 的算法爆过去，但是这是一道数论题，不是让我们用暴力乱堆堆过去的，所以我们来考虑一下性质。

平方和和加法运算能有什么关系呢……没有关系啊……反正我们 n 很小，我们可以枚举一下 a 的元素。首先我们达成共识答案肯定至少为 1，然后我们看看答案能否为 2——枚举一个 a_i, a_j(a_i > a_j)。

我们令 a_i + x = p^2, a_j + x = q^2,a_i - a_j = p^2 - q^2 = (p+q)(p - q)

这下就明晰了！枚举 a_i, a_j(a_i > a_j)，对它们差枚举因子，就能搞出来 p, q，进而就可以计算出 x，然后对整个序列都用这个 x 计算一遍就好了。

时间复杂度？枚举 a_i, a_j 是 O(n^2)，质因子 O(\sqrt{SIZE})（当然达不到这个复杂度），最后再统计一下是 O(n) 的，总共的时间复杂度就是 O(n^3\sqrt{SIZE})。这是理论上界，实践是远远达不到的，因为 a_i - a_j 不可能永远都顶到 1e9。跑不满，n 又很小，问题不大 qwq。

//SIXIANG
#include <iostream>
#include <cmath> 
#define MAXN 100000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
int a[MAXN + 10], ans = 0, n;
bool judge(int x) {
    int st = sqrt(x);
    return (st * st == x);
} 
void count(int x) {
    int cnt = 0;
    for(int p = 1; p <= n; p++)
        cnt += judge(a[p] + x);
    ans = max(ans, cnt);
}
void work(int x, int id1, int id2) {
    for(int i = 1; i * i <= x; i++) {
        if(x % i == 0) {
            int j = x / i;
            if(!((i + j) & 1)) {
                int p = (i + j) / 2;
                int q = j - p;
                int X1 = p * p - a[id1], X2 = q * q - a[id2];
                if(X1 == X2 && X1 >= 0)//X 要大于等于 0，而且 p^2 - a[i] 要等于 q^2 - a[j]
                    count(X1);

                swap(p, q);
                X1 = p * p - a[id1], X2 = q * q - a[id2];
                if(X1 == X2 && X1 >= 0)
                    count(X1);
            }
        }
    }
}
void init() {
    ans = 0;
    cin >> n;
    for(int p = 1; p <= n; p++)
        cin >> a[p];
    for(int p = 1; p <= n; p++)
        for(int i = p + 1; i <= n; i++) {
            int x = a[p] - a[i], cp = p, ci = i;
            if(x < 0) x = -x, swap(cp, ci);
            work(x, cp, ci);
        }
    cout << max(ans, 1ll) << endl;
}
signed main() {
    int T; cin >> T;
    while(T--) {
        init();
    }
}