题解归档 - cf343A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf343A
• 本地来源：problems/cf343A/idea.md
• 题目链接：https://codeforces.com/contest/343/problem/A
• 原始标题：cf343A — Rational Resistance

思路

cf343A — Rational Resistance

题意

单位电阻串联得 (R_e+1)，并联得 (\dfrac{R_e}{R_e+1})（即分子分母 ((a,b)) 变为 ((a,a+b))）。求构造最简分数 (a/b) 所需最少电阻数。

做法

与辗转相除同构：

• (a=b)：1 个电阻。
• (a>b)：先串联 (a/b) 个，余数 (a\bmod b) 递归；整除则答案为 (a/b)。
• (a<b)：先并联 (b/a) 个，余数 (b\bmod a) 递归；整除则答案为 (b/a)。

例：(3/2) → 串联 1 + 并联 2 = 3；(199/200) → 并联 1 + 串联 199 = 200。

验证

样例 + stress.py cf343A -n 500（递归解 vs 迭代解交叉对拍）。

代码

来源：problems/cf343A/solution.cpp

/* Author: likely
 * Time: 2026-06-08 06:10:00
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll f(ll a,ll b){
    if(a==b) return 1;
    if(a>b){
        ll q=a/b;
        if(a%b==0) return q;
        return q+f(a%b,b);
    }
    ll q=b/a;
    if(b%a==0) return q;
    return q+f(a,b%a);
}
int main(){
    ll a,b;
    cin>>a>>b;
    cout<<f(a,b)<<endl;
    return 0;
}