作者：风之云织2004 | 来源：互联网 | 2023-10-09 20:57
A. Rational Resistance
题意是给你很多1欧姆的电阻&＃xff0c;经过很多次的串并联之后最少需要多少电阻可以构造出 a / b
这大概是一个数论题&＃xff1f;反正标签是这样说的
虽然对于数论我不是很会
但这个题很有意思就尝试了一下
电阻的串并联大家肯定都很明白
首先像三分之一这样的电阻肯定是三个电阻串联得到的
所以几分之一就需要几个电阻并联
其他情况的话…
举个例子
比值是3 / 2 我们可以想到拆成 1 / 2 &＃43; 1&＃xff0c;这样就相当于是一个1 / 2 的电阻串联一个电阻&＃xff0c;一个1 / 2 的电阻又可以是两个电阻并联
既然 a > b 的时候可以这样想&＃xff0c;那 a > b 怎么办
这时候就不能拆成一个数加另一个数了
反过来想 a > b 可以拆成串联的状态&＃xff0c;那 a > b 就拆成并联的状态好了
这样一想 2 / 3 就可以从 1 / (3 / 2) 得到&＃xff0c;那就可以把分母拆成 1 / 2 &＃43; 1
所以对于一个比值&＃xff0c;不论是 a > b 还是 a
那就每次将大的数比小的数大的部分加到答案中&＃xff0c;然后继续将剩余的部分再进行这样的操作就好了吖
我同学告诉我这是gcd&＃xff0c;非数论选手打扰了
ll ans;
void dfs(ll n,ll m){if(n &＃61;&＃61; 0 || m &＃61;&＃61; 0) return;if(n >&＃61; m){ans &＃43;&＃61; n / m;dfs(n%m,m);}else{ans &＃43;&＃61; m / n;dfs(n,m%n);}
}int main(){ll a , b;cin >> a >> b;dfs(a , b);cout << ans;return 0;
}
京公网安备 11010802041100号