题目 | Many Perfect Squares

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,\dots ,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,\dots ,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,\dots$.

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,\dots ,a_n$ in increasing order ($1\le a_1<a_2<\dots <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,\dots ,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.

题解

核心思路

首先，$x$ 可能的取值有 ${10}^{18}$ 种，这个数据规模过于庞大。如果能减小这个规模到合适的大小，我们遍历所有可能的 $x$，找到符合条件最大的就行了。

减小 $x$ 的规模

首先我们可以确定的是，答案最小为 $1$，因为单个数可以放缩到任意完全平方数。

我们继续判断答案是否 $\ge 2$：取任意 $i,j$（$1\le i<j\le n$），判断是否存在 $x$，使 $a_i+x,a_j+x$ 均为完全平方数。若存在，则代表答案 $\ge 2$，具体的值遍历 $a_i+x$ 求得；若不存在，则说明答案 $<2$，即答案为 $1$. 最后求得所有答案的最大值即可。

由于最多有 $\frac{n(n-1)}{2}$ 种取法，因此 $x$ 的数量级大约为 $n^2$（下文会做补充），数据规模瞬间从 ${10}^{18}$ 下降到了 ${10}^3$.

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

该问题的形式化表述为：取任意 $i,j$（$1\le i<j\le n$），求解：

$$\{\begin{array}{l}{a}_i+x=u^2\\ a_j+x=v^2\end{array}$$

三个未知数 $x,u,v$ 两个方程，很明显是无穷解的。但是我们要求的是整数解，那么解的数量就有限了。下面是解法：

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

为了简洁，令 $t:=a_i-a_j$，得到：

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

将 $t$ 分为两个因子 $p,q$，即 $t=pq$，得到：

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

若 $q-p$ 为偶数，则可以构造得到解如下：（如果为奇数则这种分解方式无解）

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

回代 $u$，将 $x$ 计算出来：

$$x=u^2-a_i$$

若 $x\ge 0$，则符合条件，遍历 $a_i+x$，计算出多少个为完全平方数。（若 $<0$ 则说明这种情况不符合条件）

时间复杂度

最多 $\frac{n(n-1)}{2}$ 种取法，数量级为 $n^2$

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

$n\le$	$max\{\omega (n)\}$	$max\{d(n)\}$	$n\le$	$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$

通过遍历确定答案，数量级为 $n$

综上，时间复杂度勉强写成：$O(n^3\cdot \underset{1\le i<j\le n}{max}\{d(a_j-a_i)\})$

用 $d(n)\approx \sqrt[3]{n}$ 来近似一下，那么如果是最坏情况可以达到 ${10}^8$ 规模，有可能超时（但实际上不会，运行时间离时限还很远）

由于正因子个数的无法直接计算，而且对于一个正因子，也不一定有解，所以这个时间复杂度没办法准确表述，实际情况应该远小于上述复杂度。

代码

#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;
}