姿迷路过，对此题水的程度无语，对这个出题者的表达能力更无语

m+n-gcd(m,n)

辗转相减1，3，5，7...行、2，4，6，8...行分2组看，看第2个数的和应该分别是m,n，然而最后就缺一个最大公约数没+上去导致有1个和不对，因此要减掉

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

连int64都是40分

出题人又出数学竞赛题，这是2001年全国高中数学联赛二试第二题

附证明过程：

记所求最小值为f(m,n),可以证明f(m,n)=m+n-(m,n). ()

其中(m,n)表示m和n的最大公约数.………………………………………………10分

事实上,不妨设m≥n.

(1)关于m归纳,可以证明存在一种合乎题意的分法,使所得正方形边长之和恰为m+n-(m,n).

当m=1时,命题显然成立.

假设当m≤k时,结论成立(k≥1).当m=k+1时,若n= k+1,则命题显然成立.若n< k+1,从矩形ABCD中切去正方形AA1D1D(如图),由归纳假设矩形A1BCD1有一种分法使得所得正方形边长之和恰为m-n+n-(m-n,n)= m-(m,n).

于是原矩形ABCD有一种分法使得所得正方形边长之和为m+n- (m,n).…………20分

(2)关于m归纳可以证明()成立.

当m=1时,由于n=1,显然f (m,n)=1= m+n- (m,n).

假设当m≤k时,对任意1≤n≤m有f (m,n)= m+n- (m,n).

若m=k+1,当n= k+1时显然f(m,n)= k+1= m+n- (m,n).

当1≤n≤k时,设矩形ABCD按要求分成了p个正方形,其边长分别为a1,a2,…,ap,不妨设a1≥a2≥…≥ap.

显然a1=n或a1若a1 m+n- (m,n).

若a1=n,则一个边长分别为m-n和n的矩形可按题目要求分成边长分别为a2,…,ap的正方形,由归纳假设

a2+…+ap≥m-n+n-(m-n,n)= m- (m,n).

从而a1+a2+…+ap≥m+n-(m,n).

于是当m=k+1时,f(m,n)≥m+n- (m,n).

再由(1)可知f (m,n)=m+n- (m,n).…………………………………………………50分

program p1279;

var a,b,tmp:qword;

f:array[1..10] of qword;

i:longint;

function gcd(x,y:qword):qword;

begin

if y=0 then gcd:=x

else gcd:=gcd(y,x mod y);

end;

begin

for i:=1 to 10 do

begin

readln(a,b);

if a

30分的看过来

数据只保证了 边长小于longint 没有说答案也小于

可能是答案超过了（很正常，一直加就会） 但是边长没超过

orz出题人

这样也能下黑手

怎么回事？？？

题目说：“对于100%的数据，Ai，Bi

program p1279;

var j,k,l,m,n,a,b,ans:int64;

i:longint;

begin

for i:=1 to 10 do begin ans:=0;

readln(a,b);

if a0 do begin

l:=a div b; inc(ans,l*b);

k:=a-b*l;a:=b;b:=k;

if a

又一次沙茶了.......

第一次:全longint 崩

第二次:输出结果没有用qword 崩

第三次:除了for i:=以外全qword AC

就是一gcd.......

每次找min(i,j)边长的砍掉且保证砍掉以后仍然是一个矩形即可，因为两个正方形，能吞并则吞并，肯定更优

反正不会爆，干脆狠心点

Why ;

longint 都不行

贪心~

你可以不会图论，可以不会DP，甚至可以不会搜索，但是——

你一定要学会贪心~~~~~~~~~~~！！！

program dsa;

var a,b,c,m,n:qword;

i:longint;

begin

for i:=1 to 10 do

begin

read(a,b);

m:=a;n:=b;

c:=a mod b;

while c0 do

begin

a:=b;

b:=c;

c:=a mod b;

end;

writeln(m+n-b);

end;

end.

感谢 phl828 神牛

囧……明明说不超过maxlongint……结果用Long才30……换成unsigned long就AC了

为什么总是数学解题

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

using namespace std;

int main()

{

long long m,n,a,b,c,i,ans;

for(i=1;i>a>>b;

m=a;

n=b;

c=a%b;

while(c!=0)

{

a=b;

b=c;

c=a%b;

}

ans=m+n-b;

cout

感谢大牛赐教

var a,b,c,m,n:qword;i:longint;

begin

for i:=1 to 10 do

begin

readln(a,b);m:=a;n:=b;

c:=a mod b;

while c0 do

begin

a:=b;b:=c;c:=a mod b;

end;

writeln(m+n-b);

end;

end.

很简单的题目，哈哈，一次ac，气气你们

简单不规范地证明一下

不妨设a>b,用数学归纳法,

在a*b的正方形中删去b*b,余下(a-b)*b的矩形

由归纳假设对于f(a,b)=a+b-gcd(a,b)则

f(a-b,b)=a-b+b-gcd(a-b,b)=a-gcd(a,b)

所以f(a,b)=f(a-b,b)+b=a+b-gcd(a,b)

所以得证

a=b时容易验证也符合该式