るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

SRM 535 Div2

珍しく簡単なセットだった。

250: FoxAndIntegers

少し大きめにとった

class FoxAndIntegers {
public:
  vector <int> get(int AmB, int BmC, int ApB, int BpC) {
    vector <int> result;
    for(int a = -100;  a <= 100; a++){
      for(int b = -100;  b <= 100; b++){
	for(int c = -100;  c <= 100; c++){
	  if(a - b == AmB && b - c == BmC && a + b == ApB && b + c == BpC){
	    result.pb(a),result.pb(b),result.pb(c);
	    break;
	  }
	}
      }
    }
    return result;
  }

};




500: FoxAndGCDLCM

互いに素という事を忘れていて少し時間を無駄にした。

class FoxAndGCDLCM {
public:
  ll gcd(ll x, ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}
  ll get(ll G, ll L) {
    if(L % G != 0) return -1LL;
    ll cand = L / G;
    ll res = LONG_LONG_MAX;
    for(ll a = 1; a * a <= cand ; a += 1LL){      
      if(cand % a == 0){
	ll b = cand / a;
	if(gcd(a,b) == 1)
	  res = min(res,(a + b) * G);
      }
    }
    if(res == LONG_LONG_MAX) return -1LL;
    return res;
  }

};