AOJ 0211 Jogging

PCK本選に向けての練習
1日1ACを目標にしている。

問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0211

解法
d[i], v[i] のときの周回数を m[i] 回とし、周回時間 d[i]/v[i]*m[i]=T 時間とする(Tは一定の値)
このとき (m[i]=) T*(v[i]/d[i]) が最小となるTを求めればよい。
最小にするには T=LCM(d)/GCD(v) である。

はじめ、T=LDM(d) だと考えていてバグった。

#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAX_N = 10;
int N;
ll d[MAX_N], v[MAX_N];
ll gcd(ll a, ll b){
	if(a == 0) return b;
	return (a<=b)?gcd(b%a, a):gcd(b, a);
}
int main(){
	while(scanf("%d", &N) && N!=0){
		for(int i = 0; i < N; i++){
			scanf("%lld %lld", &d[i], &v[i]);
			int t = gcd(d[i], v[i]);
			d[i] = d[i]/t; v[i] = v[i]/t;
		}
		ll  dk=d[0], vk=v[0];
		for(int i=1; i<N; i++){
			dk = dk * d[i] / gcd(d[i], dk);
			vk = gcd(vk, v[i]);
		}
		for(int i=0; i<N; i++){
			printf("%lld\n", (v[i]/vk)*(dk/d[i]));
		}
	}
	return 0;
}