fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. // Function to check if a number is a perfect square
  6. bool isPerfectSquare(ll x) {
  7.     if (x < 0) return false;
  8.     ll r = sqrtl(x);
  9.     return r * r == x || (r + 1) * (r + 1) == x || (r - 1) * (r - 1) == x;
  10. }
  11.  
  12. int main() {
  13.     ios::sync_with_stdio(false);
  14.     cin.tie(0);
  15.  
  16.     int t;
  17.     cin >> t;
  18.     while (t--) {
  19.         int n;
  20.         cin >> n;
  21.         vector<ll> a(n);
  22.         for (int i = 0; i < n; ++i) {
  23.             cin >> a[i];
  24.         }
  25.  
  26.         int max_sq = 0;
  27.  
  28.         // Try all pairs (ai, aj)
  29.         for (int i = 0; i < n; ++i) {
  30.             for (int j = i + 1; j < n; ++j) {
  31.                 ll d = a[j] - a[i];
  32.                 vector<pair<ll, ll>> factors;
  33.  
  34.                 // Enumerate all (p, q) such that p * q = d
  35.                 for (ll f = 1; f * f <= d; ++f) {
  36.                     if (d % f == 0) {
  37.                         ll p = f, q = d / f;
  38.                         factors.push_back({p, q});
  39.                         if (p != q) {
  40.                             factors.push_back({q, p});
  41.                         }
  42.                     }
  43.                 }
  44.  
  45.                 for (auto [p, q] : factors) {
  46.                     if ((p + q) % 2 != 0 || (q - p) % 2 != 0) continue;
  47.  
  48.                     ll t = (p + q) / 2;
  49.                     ll s = (q - p) / 2;
  50.  
  51.                     ll x = t * t - a[j];
  52.                     if (x < 0) continue;
  53.  
  54.                     int count = 0;
  55.                     for (int k = 0; k < n; ++k) {
  56.                         if (isPerfectSquare(a[k] + x)) count++;
  57.                     }
  58.                     max_sq = max(max_sq, count);
  59.                 }
  60.             }
  61.         }
  62.  
  63.         // Also check x = 0
  64.         int count0 = 0;
  65.         for (int k = 0; k < n; ++k) {
  66.             if (isPerfectSquare(a[k])) count0++;
  67.         }
  68.         max_sq = max(max_sq, count0);
  69.  
  70.         cout << max_sq << '\n';
  71.     }
  72.  
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
4
5
1 2 3 4 5
5
1 6 13 22 97
1
100
5
2 5 10 17 26
stdout
copy 
2
5
1
2
https://ideone.com/hLejlP
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!