yukicoder No.356 円周上を回る3つの動点の一致

問題

No.356 円周上を回る3つの動点の一致 - yukicoder

解法

動点 P0, P1 が 1 秒ごとに近づく距離は, 1/T0 - 1/T1 です。よって, 再び出会うのにかかる時間はその逆数で表せます(この時間を t01 とします。)。

動点 P1, P2 についても同様です(再び出会うのにかかる時間を t02 とする)。

答えは, ある n, m について, t01*n = t02*m を満たす, 最小値です。

まず t01, t02 の分母を揃えるて, 分子についてはそれぞれの最小公倍数を取るようにすれば, 最小の (n, m) のペアが得られるので, 答えを求められます。

pair<ll, ll> calc(ll x, ll y) {
    ll z = y-x;
    ll w = x*y;
    ll g = __gcd(z, w);
    return make_pair(z/g, w/g);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    vector<ll> T(3);
    for (int i = 0; i < 3; i++) cin >> T[i];
    auto x = calc(T[0], T[1]);
    auto y = calc(T[0], T[2]);
    swap(x.first, x.second);
    swap(y.first, y.second);
    pair<ll, ll> z = make_pair(x.first*y.second, x.second*y.second);
    pair<ll, ll> w = make_pair(y.first*x.second, y.second*x.second);
    ll lcm = z.first/__gcd(z.first, w.first) * w.first;
    ll gcd = __gcd(lcm, z.second);
    cout << lcm/gcd << "/" << z.second/gcd << endl;
    return 0;
}