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; }