SRM 743 div1 easy

srm743d1easy.cpp

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }


const int maxn=(int)4e5+5;

class MaximizingGCD {
public:
  void divisors(int x, set<int, greater<int>>& divz) {
    divz.insert(1);
    divz.insert(x);
    for (int p=2; p*p<=x; p++) {
      if (x%p) continue;
      divz.insert(p);
      divz.insert(x/p);
    }
  }
  int maximumGCDPairing(vector <int> A) {
    set<int, greater<int>> divz;
    int n = A.size();
    for (int i=0; i<n; i++) {
      for (int j=i+1; j<n; j++) {
	divisors(A[i]+A[j], divz);
      }
    }
    for (auto d: divz) {
      map<int, int> freq;
      for (auto x: A) freq[x%d]++;
      bool good = true;
      
      for (auto p: freq) {
	int x = p.first;
	int y = (d-x)%d;
	if (x==y) {
	  if (freq[x] % 2) {
	    good = false; break;
	  }
	} else {
	  if (freq[x] != freq[y]) {
	    good = false; break;
	  }
	}
      }

      if (good) return d;
    }
    return 1;
  }
};


int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
  //cout << fixed << setprecision(6);
  MaximizingGCD g;
  vector<int> A= {46, 78, 133, 92, 1, 23, 29, 67, 43, 111, 3908, 276, 13, 359, 20, 21};
  cout<<g.maximumGCDPairing(A)<<endl;

  return 0;
}