Codeforces Round #200 (Div. 1) A. Rational Resistance

Codeforces Round #200 (Div. 1) の練習会に参加しました。ABC 解けてそこそこです(Div. 1 で3 問解けたことなんて多分 1 度もない)。

問題

Codeforces

解法

a/b が 1 以上なら 1 + 1 + ... + 1 + (1 未満の分数) という形にします。
a/b が 1 未満ならその逆数である b/a を作れればそれを並列につなげれば良いので b/a を作ることを目指すことになります。

こんな感じで a/b = 1 になることがあったらそれは抵抗 1 つで表現できるので終わりです。

まとめてみると, ユークリッドの互除法をやっていることになります。

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    ll ans = 0;
    while (1) {
        if (a == 0) break;
        if (a > b) {
            ans += a/b;
            a %= b;
        } else if (a == b) {
            ans += 1;
            break;
        } else {
            swap(a, b);
        }
    }
    cout << ans << endl;
    return 0;
}