Many Perfect Squares

Created by LXC on Sat Jun 3 00:24:40 2023

https://codeforces.com/problemset/problem/1781/D

ranting: 1800

tag: brute force, math, number theory

problem

给出n个不同的升序排序的数（n≤50），如果给这n个数都加一个正整数使得n个数中平方数最多，最多是多少。

solution

对于任意两个数$a_i$和$a_j$，$i<j$。考虑所有的非负整数k，使得这两个数加上k成为平方数。

任意两个数$a_j$和$a_i$的差值可以分解为两个数$q-p$和$p+q$的乘积，只需枚举其因子，便得知$q-p$和$q+p$，进一步可以解出$p$和$q$。测试$x=q^2-a_j$时有多少个数加上x会成为平方数，维护这个数最大即可。

设$p^2 = a_i+x$，$q^2 = a_j + x$

$q^2 - p^2 = (q-p)(q+p) = a_j-a_i$

设$x = q-p$，$y = q + p$。

$q = \frac{x+y}{2}$，若$q^2-a_j$非负便找到了一个可测的$x$。

code

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

void sol() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int ans = 1;
    auto check = [&](ll x) {
        int c = 0;
        for (ll i : a) {
            ll s = sqrt(i + x);
            if (s * s == x + i) {
                c++;
            }
        }
        ans = max(ans, c);
    };
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ll pq = a[j] - a[i];
            for (int k = 1; k * k <= pq; k++) {
                if (pq % k == 0) {
                    ll p = (k + pq / k) / 2;
                    if (p * p - a[j] >= 0) {
                        check(p * p - a[j]);
                    }
                }
            }
        }
    }
    cout << ans << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}