Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round)

D. Many Perfect Squares

https://codeforces.com/contest/1782/problem/D

4 seconds / 512 megabytes

standard input / standard output

## Problem

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}$.

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.

## 题解

#### 给定一对数如何求解 $x$

$$\begin{cases} a_i+x=u^2\\ a_j+x=v^2 \end{cases}$$

\begin{align} 两式相减&\Rightarrow a_i-a_j=u^2-v^2\\ &\Rightarrow a_i-a_j=(u+v)(u-v)\\ \end{align}

$$t=(u+v)(u-v)$$

$$pq=(u+v)(u-v)$$

$$\begin{cases} \displaystyle{u=\frac{q-p}{2}}\\\\ \displaystyle{v=\frac{q+p}{2}} \end{cases}$$

$$x=u^2-a_i$$

#### 时间复杂度

$x$ 的正因子个数为 $d(x)$，这个数值无法用表达式直接确定，但可以查表确定最大值为 $1344$.

$n\leq$$\max\{\omega(n)\}$$\max\{d(n)\}$$n\leq$$\max\{\omega(n)\}$$\max\{d(n)\} 10^1$$2$$4$$10^9$$9$$1344$
$10^2$$3$$12$$10^{10}$$10$$2304 10^3$$4$$32$$10^{11}$$10$$4032$
$10^4$$5$$64$$10^{12}$$11$$6720 10^5$$6$$128$$10^{13}$$12$$10752$
$10^6$$7$$240$$10^{14}$$12$$17280 10^7$$8$$448$$10^{15}$$13$$26880$
$10^8$$8$$768$$10^{16}$$13$$41472 10^9$$9$$1344$$10^{17}$$14$$64512$
$10^{10}$$10$$2304$$10^{18}$$15$$103680$

## 代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

bool is_square(int n)
{
int r = sqrt(1.0L * n);
return r * r == n;
}

void solve()
{
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
int ans = 1;
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
int t = a[j] - a[i];
for (int p = 1; p * p <= t; p++)
{
if (t % p)
continue;
int q = t / p;
if ((q - p) % 2)
continue;
int u = (q - p) / 2, v = (q + p) / 2;
int x = u * u - a[i];
if (x < 0)
continue;
int res = 0;
for (int ii = 0; ii < n; ii++)
if (is_square(a[ii] + x))
res++;
ans = max(ans, res);
}
}
}
cout << ans << endl;
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--)
solve();
return 0;
}