题解

75 条题解

  • 2
    @ 2008-09-24 14:35:21

    给大家解释一下为什么是a+b-gcd(a,b)吧。。。。

    首先,对于一个矩形,要按照题目要求分解出最小边长和的若干个正方形,应该分的越少越好,因此,当a>b时,我们应该分出一个边长为b的正方形,之后,剩下的部分是一个(a-b)*b的矩形,我们再分解出一个变长为min(b,a-b)的正方形,如此往复,最终剩下的一个矩形自然是一个正方形,而这歌正方形的边长自然是gcd(a,b){我们之前其实就是做了一个更相减损法个工作。。。},这是,我们实际分解出的边长和是a+b-gcd(a,b)(最后一个正方形只需要计算一边长,因此减去一个边长)

    明白?

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 0ms

    ├ 测试数据 09:答案正确... 0ms

    ├ 测试数据 10:答案正确... 0ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:0ms

  • 1
    @ 2021-03-18 10:12:58
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;
        
        ll a,b;
        
        void main()
        {
            while (~scanf("%lld%lld",&a,&b))
            {
                ll ans=0;
                if (a<b)
                    swap(a,b);
                for (ll i=a,j=b;j!=0;)
                {
                    ans+=i-(i%j);
                    ll tmpi=i,tmpj=j;
                    i=tmpj,j=tmpi%tmpj;
                }
                printf("%lld\n",ans);
            }
        }
    };
    
    int main()
    {
        dts::main();
    }
    
    #include <cmath>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <algorithm>
    #include <vector>
    #include <deque>
    using namespace std;
    
    namespace dts
    {
        typedef long long ll;   
    
        ll gcd(ll a,ll b)
        {
            if (a%b==0)
                return b;
            else
                return gcd(b,a%b);
        }
        
        ll a,b;
        
        void main()
        {
            while (~scanf("%lld%lld",&a,&b))
                printf("%lld\n",a+b-gcd(a,b));
        }
    }
    
    int main()
    {
        dts::main();
    }
    
  • 0
    @ 2017-10-17 14:38:40

    最纯粹的欧几里得

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    long long a,b,ans,gg,jie,minn,maxx;
    void gcd(long long x,long long y)
    {
        if(y==0) return;
        if(y==x)
        {
            ans+=x;
            return;
        }
        else
        {
            minn=min(x,y);
            gg=x/y;
            jie=gg*minn;
            ans+=jie;
            gcd(y,x%y);
        }
    }
    int main()
    {
        for(int i=1;i<=10;i++)
        {
            minn=0;
            maxx=0;
            cin>>a>>b;
            minn=min(a,b);
            maxx=max(a,b);
            gcd(maxx,minn);
            cout<<ans<<endl;
            ans=0;
        }
        return 0;
    }
    
  • 0
    @ 2017-06-23 10:13:10
    //简单粗暴,类似于贪心的算法,一直取最大的正方形
    #include <bits/stdc++.h>
     using namespace std;
    int main()
    {
        int num = 10;
        long long a, b;
        long long ans = 0;
        while(num--)
        {
            ans = 0;
            cin >> a >> b;
            while(a != 0 && b != 0)
            {
                if(a > b)
                {
                    ans += a / b * b;
                    a -= a / b * b;
                }
                else if(a < b)
                {
                    ans += b / a * a;
                    b -= b / a * a;
                }
                else if(a == b)
                {
                    ans += a;
                    a -= b;
                }
            }
            cout << ans << endl;
        }
        return 0;
    }
    
  • 0
    @ 2016-11-09 21:40:33

    类似求gcd

    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    typedef long long ll;
    
    ll dfs(ll a,ll b)       //a:长边  b:短边
    {
        if (b==1) return a;         //边长为1的长方形
        if (b==0) return 0;         //正方形
        return b*(a/b)+dfs(max(a%b,b),min(a%b,b));
    }
    
    int main()
    {
        for (int i=0;i<10;i++) {
            ll a,b; cin>>a>>b;
            cout<<dfs(max(a,b),min(a,b))<<endl;
        }
    }
    
  • 0
    @ 2016-11-07 10:58:56

    这题数据要用long long。。。。

  • 0
    @ 2016-09-08 14:02:38

    a+b-gcd(a,b)。。。
    输入开始用了scanf。。。卡了我好久。。。擦咧、我的AC率啊~
    c++
    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #define LL unsigned long long
    using namespace std;
    LL gcd(LL x,LL y)//无聊写个GCD优化版
    {
    LL i,j;
    if ( x == 0 )
    return y;
    if ( y == 0 )
    return x;
    for ( i = 0; 0 == (x&1); ++i ) x>>=1;
    for ( j = 0; 0 == (y&1); ++j ) y>>=1;
    if ( j<i ) i = j;
    while (1)
    {
    if ( x<y ) x ^= y,y ^= x,x ^= y;
    if ( 0 == (x -= y) ) return y<<i;
    while ( 0 == (x&1) ) x >>= 1;
    }
    }
    int main()
    {
    LL a,b;
    for (int i=1;i<=10;i++)
    {
    cin>>a>>b;
    cout<<a+b-gcd(a,b)<<endl;
    }
    return 0;
    }

  • 0
    @ 2016-08-23 03:50:10

    #include"stdio.h"
    #define swap(a,b) long long t=a;a=b;b=t
    typedef long long ll;
    int main()
    {
    ll a,b;
    while(scanf("%I64d%I64d",&a,&b)!=EOF)
    {

    ll ans=0;
    for(;;)
    {
    if(a>b){swap(a,b);}
    if(b%a==0) {ans+=a*(b/a);break;}
    else{ll ta=a,tb=b;ans+=a*(b/a);a=tb%ta;b=ta;}
    }
    printf("%I64d\n",ans);
    }
    return 0;
    }

  • 0
    @ 2016-02-20 17:48:10

    #include<iostream>
    #define ULL unsigned long long
    using namespace std;
    ULL f(ULL a,ULL b)
    {
    if(b==0)return 0;
    return (a/b)*b+f(b,a%b);
    }
    ULL a,b;
    int main()
    {
    while(cin>>a>>b)
    cout<<f(a,b)<<endl;
    return 0;
    }

  • 0
    @ 2016-02-20 17:47:48
        #include<iostream>
        #define ULL unsigned long long
        using namespace std;
        ULL f(ULL a,ULL b)
        {
            if(b==0)return 0;
            return (a/b)*b+f(b,a%b);
        }
        ULL a,b;
        int main()
        {
            while(cin>>a>>b)
            {
                cout<<f(a,b)<<endl;
            }
            return 0;
        }
    
  • 0
    @ 2015-10-27 01:44:53

    #include <iostream>
    #include <cstdio>

    using namespace std;

    int main()
    {
    long long int a[10];
    long long int b[10];
    long long int ans[10];
    long long int i,j;
    for(i=0;i<10;i++)
    {
    //scanf("%lld%lld",&a[i],&b[i]);
    cin>>a[i]>>b[i];
    ans[i]=0;
    while(a[i]&&b[i])
    {
    if(a[i]>b[i])
    {
    j=a[i]/b[i]*b[i];
    ans[i]+=j;
    a[i]-=j;

    continue;
    }
    else
    {
    j=b[i]/a[i]*a[i];
    ans[i]+=j;
    b[i]-=j;

    continue;
    }
    /*
    long long t=b/a*a;
    ans += t;
    b -= t;
    */
    }
    }
    for(i=0;i<10;i++)
    {
    cout<<ans[i]<<endl;
    //printf("%lld\n",ans[i]);
    }

    return 0;
    }

  • 0
    @ 2015-10-05 22:20:32

    #include<iostream>
    #include<algorithm>
    using namespace std;

    int main(){
    long long a,b;
    for(int i=1;i<=10;i++){
    cin>>a>>b;
    long long ans=0;
    while(a && b){
    if(a>b)swap(a,b);

    long long t=b/a*a;
    ans += t;
    b -= t;
    }
    cout<<ans<<endl;
    }

    return 0;
    }

  • 0
    @ 2015-08-31 15:01:40

    都要用long long 类型的
    #include<cstdio>
    #include<iostream>
    using namespace std;
    long long x,y,t,ans=0;
    int main()
    {
    freopen("p1279.in.txt","r",stdin);
    for(int i=1;i<=10;i++)
    {
    ans=0;
    scanf("%lld%lld",&x,&y);
    long long j=max(x,y);
    long long k=min(x,y);
    while(k!=0)
    {
    ans+=j/k*k;
    t=k;
    k=j%k;
    j=t;
    }
    printf("%lld\n",ans);
    }
    return 0;
    }

  • 0
    @ 2015-08-04 21:13:08

    超时了两个点啊。@*@
    program exam;
    var i,j,m,n,k,l,s,p:longint;
    a,b:array[0..10] of longint;
    procedure kk(x,y:longint);
    begin
    if x=y then begin s:=s+x; exit; end;
    while x>y do
    begin
    dec(x,y);
    inc(s,y);
    if x=y then begin s:=s+x; exit; end;
    if x<y then begin kk(y,x); break; end;
    end;
    end;
    begin
    assign(input,'1.txt');
    reset(input);
    for i:=1 to 10 do
    begin
    s:=0;
    readln(a[i],b[i]);
    if a[i]<b[i] then
    begin
    p:=a[i]; a[i]:=b[i]; b[i]:=p;
    end;
    kk(a[i],b[i]);
    writeln(s);
    end;
    end.

  • 0
    @ 2015-07-31 18:07:46

    #include<iostream>
    #include<cstring>
    #include<algorithm>
    using namespace std;

    long long int gcd(long long int a, long long int b){
    if(a%b == 0)
    return a/b*b;
    return a/b*b + gcd(b, a%b);
    }

    int main()
    {
    long long int a,b;
    for(int i=1; i<=10; i++){

    cin>>a>>b;
    cout<<gcd(a, b)<<endl;
    }
    system("pause");
    return 0;
    }

  • 0
    @ 2014-10-29 08:02:51

    #include<iostream>
    using namespace std;
    long long A, B, C;
    void gcd(long long a, long long b)
    {
    if(b == 0)return;
    C += a - a % b;
    gcd(b, a % b);
    }
    int main(){
    while(cin >> A)
    {
    cin >> B;
    C = 0;
    gcd(A, B);
    cout << C << endl;
    }
    return 0;
    }

  • 0
    @ 2014-08-17 12:42:18

    #include <iostream>
    using namespace std;
    int main()
    {
    long long int m,n,a,b,c,i,ans;
    for(i=1;i<=10;i++)
    {
    cin>>a>>b;
    m=a;
    n=b;
    c=a%b;
    while(c!=0)
    {
    a=b;
    b=c;
    c=a%b;
    }
    ans=m+n-b;
    cout<<ans<<endl;
    }
    //system("pause");
    return 0;
    }
    a+b-gcd(a,b) 基础数论 精度long long int足够 题中说过了~

  • 0
    @ 2014-08-10 00:07:57

    program p1279;
    var a1,b1,min:int64;
    i:longint;
    //
    procedure gcd(a,b:int64);
    begin
    if b=0 then exit;
    inc(min,b*(a div b));gcd(b,a mod b);
    end;
    //
    begin
    for i:=1 to 10 do
    begin
    readln(a1,b1);
    min:=0;gcd(a1,b1);
    writeln(min);
    end;
    end.

  • 0
    @ 2013-11-02 16:28:24

    !!int64 跪了。。简单题更容易做的太仓促。。。

  • 0
    @ 2013-10-29 20:49:29

    var j,k,a,b,Ans,AA,BB:Int64;
    i:Longint;

    Function Euclid(A,B:Int64):Int64;
    Begin
    If B=0 then Exit(A);
    Exit(Euclid(B,a mod b));
    End;

    Begin
    For i:=1 to 10 do
    Begin
    Readln(AA,BB);
    Writeln(AA+BB-Euclid(AA,BB));
    End;
    End.

信息

ID
1279
难度
5
分类
数论 | 欧几里得算法 点击显示
标签
(无)
递交数
1840
已通过
683
通过率
37%
被复制
9
上传者