SRM 365 Div1 Medium ArithmaticProgressions

問題

やりかた

以下ソース。

class ArithmeticProgressions {  
public:
  ll N, m, M;
  vector<ll> s;

  ll floor(ll a, ll b){
    ll m = a % b;
    if(m < 0) m += b;
    return (a - m) / b;
  }
  ll ceil(ll a, ll b){
    ll m = a % b;
    if(m < 0) m += b;
    if(m > 0) m = b - m;
    return (a + m) / b;
  }
  vector <string> maxAptitude(vector <string> numbers) {
    vector <string> ans;
    N = numbers.size();
    s.clear();
    for(int i = 0; i < N; i++) s.push_back(s2i(numbers[i]));
    sort(ALL(s));

    m = s[0], M = s[N - 1];
    ll P = 0, Q = 1;
    for(int i = 0; i < N; i++){
      for(int j = i + 1; j < N; j++){
	for(int k = j + 1; k < N; k++){
	  ll g = gcd(s[j] - s[i], s[k] - s[j]);

	  ll p = 0, q = 0;
	  for(int a = 0; a < N; a++) 
	    if(s[a] % g == s[i] % g) p++;
	  
	  q = floor(M - s[i], g) - ceil (m - s[i], g) + 1;

	  ll gg = gcd(p, q);
	  p /= gg, q /= gg;
	  if(P * q < p * Q) P = p, Q = q;
	}
      }
    }
    ans.push_back(i2s(P));
    ans.push_back(i2s(Q));
    return ans;
  }
};