fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int Mod=998244353;
  5.  
  6.   bool is_square(ll num) {
  7.     ll root = sqrt(num);
  8.     return root * root == num;
  9. }
  10.  
  11. void solve() {
  12.  
  13.    int n;
  14.    cin >> n;
  15.    vector<int> a(n);
  16.    for(int i=0;i<n;i++) cin >> a[i];
  17.  
  18.    ll ans =1;
  19.    for(int i=0;i<n;i++){
  20.     ll curr=0;
  21.     for(int j=i+1;j<n;j++){
  22.  
  23.         ll d=a[j]-a[i];
  24.         vector<pair<ll,ll>> divisors;
  25.  
  26.         for(int k=1;k*k<=d;k++){
  27.           if(d%k==0){
  28.             ll p=k , q=d/k;
  29.             divisors.push_back({p,q});
  30.             if(p!=q)
  31.              divisors.push_back({q,p});
  32.           }
  33.         }
  34.  
  35.        for(int q=0;q<divisors.size();++q){
  36.           if((divisors[q].first+divisors[q].second)%2!=0 || (divisors[q].first-divisors[q].second)%2!=0) continue;
  37.  
  38.           ll t =(divisors[q].first+divisors[q].second)/2;
  39.           ll s =(divisors[q].first-divisors[q].second)/2;
  40.           if(t*t < a[j]) continue;
  41.           ll x=t*t-a[j];
  42.           ll cnt=0;
  43.  
  44.           for(int k=0;k<n;k++)
  45.             if(is_square((ll)a[k]+x)) cnt++;
  46.  
  47.           curr=max(curr,cnt);
  48.        }
  49.     }
  50.     ans=max(ans,curr);
  51.    }
  52.    cout << ans << '\n';
  53.  
  54. }
  55.  
  56. int main(){ 
  57.     ios::sync_with_stdio(false);
  58.     cin.tie(nullptr);
  59.  
  60.     int t;
  61.     cin >> t;
  62.     while (t--) solve();
  63.  
  64.  
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5296KB
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/cxCobw
language:
C++ (gcc 8.3)
created:
1 day 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!