CF1781D 解题乱弹

标签：CF1781D 乱弹 复杂度 int 枚举 解题 X1 我们 define

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();
	}
}

标签：CF1781D,乱弹,复杂度,int,枚举,解题,X1,我们,define
From： https://www.cnblogs.com/thirty-two/p/17112632.html