D. Many Perfect Squares
You are given a set $a_1, a_2, \ldots, a_n$ of distinct positive integers.
We define the squareness of an integer $x$ as the number of perfect squares among the numbers $a_1 + x, a_2 + x, \ldots, a_n + x$.
Find the maximum squareness among all integers $x$ between $0$ and $10^{18}$, inclusive.
Perfect squares are integers of the form $t^2$, where $t$ is a non-negative integer. The smallest perfect squares are $0, 1, 4, 9, 16, \ldots$.
Input
Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$). The description of the test cases follows.
The first line of each test case contains a single integer $n$ ($1 \le n \le 50$) — the size of the set.
The second line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ in increasing order ($1 \le a_1 < a_2 < \ldots < a_n \le 10^9$) — the set itself.
It is guaranteed that the sum of $n$ over all test cases does not exceed $50$.
Output
For each test case, print a single integer — the largest possible number of perfect squares among $a_1 + x, a_2 + x, \ldots, a_n + x$, for some $0 \le x \le 10^{18}$.
Example
input
4 5 1 2 3 4 5 5 1 6 13 22 97 1 100 5 2 5 10 17 26
output
2 5 1 2
Note
In the first test case, for $x = 0$ the set contains two perfect squares: $1$ and $4$. It is impossible to obtain more than two perfect squares.
In the second test case, for $x = 3$ the set looks like $4, 9, 16, 25, 100$, that is, all its elements are perfect squares.
解题思路
首先对于任意一个$a_i$都一定存在一个$x$使得$a_i + x$是一个完全平方数,因此答案至少是$1$。然后接下来考虑答案至少是$2$的情况,如果存在$a_i + x$和$a_j + x$均是完全平方数,那么如果最终至少存在$3$个完全平方数,就必定会包含$a_i + x$和$a_j + x$,可以发现此时$x$已经固定了,因此我们只需要枚举数组看看有多少个$a_k + x$是完全平方数就可以了。
$n$最大为$50$,因此可以枚举所有$a_i$和$a_j$的组合,这里假设$a_i > a_j$。那么假设有$a_i + x = n^2$,$a_j + x = m^2$,这里求解$x$并不是直接枚举$x$,而是两式做差得到$a_i - a_j = n^2 - m^2 = (n - m)(n + m)$,再把因式分解看作$(n - m)(n + m) = p \cdot q$,其中$p < q$。即有$a_i - a_j = p \cdot q$,这时就可以用试除法来求出$a_i - a_j$的因子$p$,从而得到$q = \frac{a_i - a_j}{p}$。
因此有$$\begin{cases} n - m = p \\ n + m = q \end{cases}$$
解方程得到$n = \frac{p + q}{2}$,$m = \frac{q - p}{2}$,有解条件是$2 \mid p + q$以及$2 \mid q - p$,即$p$和$q$的奇偶性要相同。所以$x = n^2 - a_i = \left( \frac{p + q}{2} \right)^2 - a_i$,这里的$x$还要满足$0 \leq x \leq {10}^{18}$。然后再枚举一遍序列统计有多少个$a_k + x$是完全平方数就可以了。
这里再补充个细节。实际上$x$只需要判断是否满足$x \geq 0$就行了,不需要再判断是否满足$x \leq {10}^{18}$,因为$x$是一定不会超过${10}^{18}$,注意到$x = \left( \frac{p + q}{2} \right)^2 - a_i < \frac{(p+q)^2}{4} < (p + q)^2$,而$p + q \leq p \cdot q + 1 = a_j - a_i + 1 \leq {10}^9$,因此$x < {\left({10}^9\right)}^2 = {10}^{18}$。
当$p > 1$,$q > 1$,那么有$(p - 1)(q - 1) \geq 1$,即$p \cdot q - p - q + 1 \geq 1$,即$p \cdot q \geq p + q$。而当$p = 1$,那么$q = a_i - a_j$,因此$p + q = a_j - a_i + 1$。注意这里$a_i - a_j \in [1, {10}^9)$。
在不超过${10}^9$的数中,一个数最多有$1344$个因子,因此时间复杂度为$O(n^2 \sqrt{{10}^9} + {1344} \cdot n^3)$。
AC代码如下:
1 #include <bits/stdc++.h> 2 using namespace std; 3 4 typedef long long LL; 5 6 const int N = 60; 7 8 int a[N]; 9 10 int check(LL x) { 11 LL t = sqrt(x); 12 return t * t == x; 13 } 14 15 void solve() { 16 int n; 17 scanf("%d", &n); 18 for (int i = 0; i < n; i++) { 19 scanf("%d", a + i); 20 } 21 sort(a, a + n); 22 int ret = 1; 23 for (int i = 0; i < n; i++) { 24 for (int j = 0; j < i; j++) { 25 int s = a[i] - a[j]; 26 for (int k = 1; k <= s / k; k++) { // 求s的因子 27 if (s % k == 0) { 28 int p = k, q = s / k; 29 if (p % 2 == q % 2) { // p和q要同奇偶性才有解 30 LL x = 1ll * (p + q) * (p + q) / 4 - a[i]; 31 if (x < 0 || x > 1e18) continue; // x要在满足的范围内 32 int t = 0; 33 for (int u = 0; u < n; u++) { // 统计有多少个数加上x后是完全平方数 34 t += check(a[u] + x); 35 } 36 ret = max(ret, t); 37 } 38 } 39 } 40 } 41 } 42 printf("%d\n", ret); 43 } 44 45 int main() { 46 int t; 47 scanf("%d", &t); 48 while (t--) { 49 solve(); 50 } 51 52 return 0; 53 }
参考资料
Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) A-D:https://www.cnblogs.com/BlankYang/p/17056807.html
Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) D (数论+思维/DP+map):https://zhuanlan.zhihu.com/p/599387918
力扣第324场周赛:https://www.bilibili.com/BV1wD4y1h7Vz/
标签:Perfect,10,le,squares,int,Many,18,test,Squares From: https://www.cnblogs.com/onlyblues/p/17061544.html