みんなでジョギング

パソコン甲子園2009 問題07 みんなでジョギング

問題文

同じスタート地点にいるn人の人がそれぞれ1周di(km)のコースをvi(km/h)で走り続けるとき、全員が再びスタート地点で同時に出会ったときの、それぞれの周回数を求める問題です。

n人をそれぞれ0～n-1の番号iで表すことにします。まず、計算途中でのオーバーフローを避けるために、それぞれのvi/diを約分します。次にvi/di (i = 0 ～ n-1)を通分します。全ての分母diに対する最小公倍数LCMを分母とすると、それぞれの分子はvi×LCM/diとなります。最後に全ての分子をそれらの最大公約数で割ると、最初に全員が出会う周回数となります。最大公約数を求めるためにはユークリッドの互除法を用います。

#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ullong;
#define MAX 10

ullong gcd(ullong a, ullong b){
    return ( b == 0 ) ? a : gcd(b, a%b);
}

ullong lcm( ullong a, ullong b ){
    if ( b > a ) swap(a, b);
    return a/gcd(a, b)*b;
}

void compute(int n){
    ullong d1, d2, v1, v2, G;
    pair<ullong, ullong> S[MAX];
    for ( int i = 0; i < n ; i++ ){
	cin >> S[i].first >> S[i].second;
	G = gcd(S[i].first, S[i].second);
	S[i].first /= G;
	S[i].second /= G;
    }

    ullong l = lcm(S[0].first, S[1].first);
    for ( int i = 2; i < n; i++ ) l = lcm(l, S[i].first);
    
    ullong A[MAX];
    for ( int i = 0; i < n; i++ ) A[i] = S[i].second*(l/S[i].first);
    G = gcd(A[0], A[1]);
    for ( int i = 2; i < n; i++ ) G = gcd(G, A[i]);
    for ( int i = 0; i < n; i++ ) cout << A[i]/G << endl;
}

main(){
    int n;
    while( cin >> n && n ) compute(n);
}