POJ 1855 Mint

問題

数種類の長さの棒がある。各種類とも棒は無尽蔵にあるとして良い。棒をつなぎ合わせて4本足の机を作る。各足は同じ種類の木を使い、4本の足の長さが揃うように作る時、決められた高さ以下で作れる最高の高さと、決められた高さ以上で作れる最小の高さを求めよ。

やりかた

ある4種類を選んだ時、その4種類の長さの公倍数のうち、決められた高さ以下で最高になるものと、高さ以上で最低になるものを計算する。すべての4種類のパターンについてこの計算を行い、最高値と最小値を求める。
長さの種類数がが50以下なので4重ループで通る。

以下ソース。

inline ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b, a % b); }
inline ll lcm(ll a, ll b){ return a / gcd(a, b) * b; }

int e[51];

int main(int argc, char **argv){
  int N, M;
  while(cin >> N >> M, N + M){
    for(int i = 0; i < N; i++) cin >> e[i];
    sort(e, e + N);
    int v[4];
    while(M--){
      ll T; cin >> T;
      ll miv = 0, mav = LLINF;
      for(int a = 0; a < N; a++){
	for(int b = a + 1; b < N; b++){
	  for(int c = b + 1; c < N; c++){
	    for(int d = c + 1; d < N; d++){
	      v[0] = e[a], v[1] = e[b], v[2] = e[c], v[3] = e[d];
	      ll g = v[0];
	      for(int j = 0; j < 4; j++)
		g = lcm(g, v[j]);
	      
	      miv = max(miv, T / g * g);
	      mav = min(mav, (T + g - 1) / g * g);
	    }
	  }
	}
      }
      cout << miv << " " << mav << endl;
    }      
  }
  return 0;
}