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个点时间超限了！

（下了个数据）

5001 3996791551891436541 4103700785283928741 3396532698133927071 5765301574293217201 9657412226008298281 4241853992450155721 4325552770440642021 2270385924372396131 6453263673281469341 8120403028681095571 2546725598229957541 7778108363871416291 9321844586008298941 7708589651935079251 5888471701702449721 4795763256264451201 1214810295218721241 6051057122284199011 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
     
      #include
      
       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
      
     

End

这道题我会，还是WA了！！！

今天又是爆0的一天啊……