75 条题解
-
3
maddog LV 3 @ 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
Sky1231 (sky1231) LV 10 @ 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
westfallon LV 8 @ 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
Empire-003 LV 9 @ 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
类似求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
MarkAllenWeiss LV 8 @ 2016-11-07 10:58:56
这题数据要用long long。。。。
-
0
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
#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
zcq784951623 LV 8 @ 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
#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
#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
都要用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
zhuchenglong LV 8 @ 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
#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
#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足够 题中说过了~
maddog
LV 3
@ 2008-09-24 14:35:21
