2322. capacitor
(File IO): input:capacitor.in output:capacitor.out
题目描述
输入
输出
样例输入
样例输出
数据范围限制
Solution
注意这句话
温暖了这道题目~
首先我要解释一下并联和串联的意义：
将$frac ab$与1串联
$mathsf{frac {1}{frac ba + frac 11}}$
$=frac{1}{frac{a+b}{a}}$
$=frac{a}{a+b}$
将$frac ab$与1并联
$ frac ab + 1$
$=frac {a+b} {a} $
所以，经过一次操作后，实际上只是把分子加上了分母或者是把分母加上了分子！
接下来
对于任何一个分数$frac ab$，首先将其化成最简分数（约分），再提取整数部分，最后再代回$frac ab$
倒过来推导之前的过程：将a，b中大的数减去小的数，直到两者皆为1
于是，我竟然有4个点时间超限了！
（下了个数据）
500 1 399679155189143654 1 410370078528392874 1 339653269813392707 1 576530157429321720 1 965741222600829828 1 424185399245015572 1 432555277044064202 1 227038592437239613 1 645326367328146934 1 812040302868109557 1 254672559822995754 1 777810836387141629 1 932184458600829894 1 770858965193507925 1 588847170170244972 1 479576325626445120 1 121481029521872124 1 605105712228419901 1 630952467219952791 …………
好厉（wei）害（suo）！
再优化
我优化了两个地方：
求gcd使用二进制法以及卡常（可无视）
以及
减少相减循环的次数
当a，b反复相减时，总有一个数会先变成1（假设是a），然后b又要执行b次运算，每次仅仅是把b-=1，ans++……这个地方一定可以优化！
直接在a，b有一者减成1时跳出循环（假设是a）
本来还有b次循环，那么这时的答案就会比正确答案少b
所以，最后再把ans+=a*b即可
（上面的式子对a=1或b=1都适用）
Code
#include<iostream> #include<cstdio> using namespace std; long long a,b,ans,t,g,n; long long gcd(long long a,long long b) { if(!b) return a; if(!(a|0)&&!(b|0)) return 2*gcd(a>>1,b>>1); if((!(a|0))&&(b|0)) return gcd(a,b>>1); if(!(a|0)&&!(b|0)) return gcd(a>>1,b); return gcd(b,a%b); } int main() { // freopen("capacitor.in","r",stdin); // freopen("capacitor.out","w",stdout); cin>>t; while(t--) { scanf("%lld%lld",&a,&b); ans=0; g=gcd(a,b); a/=g;b/=g; n=a/b; if(a>b) swap(a,b); while(a!=1&&b!=1) { ans++; b-=a; if(a>b) swap(a,b);//a<b } cout<<ans+a*b<<endl; } return 0; }
End
这道题我会，还是WA了！！！
今天又是爆0的一天啊……