小学生问题,是不是难了点? - 辕门射虎 - 轩辕春秋文化论坛 20周年


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#1

发表于 2006-8-5 22:20 资料个人空间短消息只看该作者

小学生问题,是不是难了点?

一个矩形由a*b个同样大小的小正方形组成,l为其对角线,求l穿过的小正方形个数.

ps:原题是证明题,不过来这的各位都是高手,就改成问答题了.

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	金圭子


	白衣伯爵中大夫 ★

组别	白衣卿相
级别	征西将军
好贴	4
功绩	265
帖子	4926
编号	27961
注册	2004-12-16

#2

发表于 2006-8-6 03:14 资料文集短消息只看该作者

嗯，暂时先给个结论…………，对着ps一种种画，然后用枚举法枚举出来的：
情况1.如果a=b，则答案为a；这个很好理解
情况2.如果a为b的整数倍（反之亦然），那答案为a（如果b是a的整数倍则为b）；
这个也很好理解，稍微解说一下吧：设a/b=m，把大矩形分成b*b个小矩形，每个矩形为m*1，则每个小矩形对角线穿过m条，总共穿过m*b=a条。其实情况1可以作为情况2的特例，即m=1。

情况3.如果ab互质，则答案为a+b-1；这个也很好证明，
困了，所以简单说一下吧：既然ab互质，则对角线不可能从小正方形的对角线穿过，只能从小正方形的边穿过。所以从大矩形一头到另一头，必须穿过a-1个横边和b-1个直边，每次穿过都会进入一个新的小正方形，而且因为对角线是直线所以不会出现穿过同一个小正方形两次的情况。加上出发的一个小正方形，总计穿过小正方形a-1+b-1+1=a+b-1

情况4.最后，最小公约数既不为1也不为a或者b，就是说如果a和b不互质，也不是一方是另一方的整数倍。则设a、b的最小公约数(a,b)=n（(a,b)是a和b的最小公约数的意思），a/n=c，b/n=d。则可以把图分为n*n个小图，每个图为c*d，其中cd互质，则穿过c*d小矩形对角线的条数为c+d-1，总条数为(c+d-1)*n，即为a+b-n。
而且情况2、情况3可以看作情况4的两个特例，前者为(a,b)=b，后者为(a,b)=1。

所以最终的答案是：(a+b)-(a,b)
（这样是不是样子比较好看啊^_^）

[广告] 真诚支持说岳，携手共创辉煌


	shareblue

组别	百姓
级别	破贼校尉
功绩	1
帖子	71
编号	74203
注册	2006-6-30

#3

发表于 2006-8-6 03:34 资料短消息只看该作者

回复 #1 KYOKO 的帖子

呵呵, LZ严重了.....

回你道题吧: 分解质因数!! 也是儿童题

分解质因数: 2647398563758362810978379

呵呵, 一个道理........

[广告] 《精忠报国岳飞传完整版》火热发布


	nncaojian (盘蛇枪)

组别	百姓
级别	在野武将
功绩	0
帖子	15
编号	78125
注册	2006-8-5

#4

发表于 2006-8-7 03:09 资料短消息只看该作者

我要原题！！强烈要求哦！！！！！！！！1

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	KYOKO (★御姐控★)


	唐国公荆南节度使 ★★

组别	节度使
级别	大将军
功绩	1456
帖子	65615
编号	32
注册	2003-8-19
来自	BWL

#5

发表于 2006-8-7 12:22 资料个人空间短消息只看该作者

原题就是证明答案是

a+b)-(a,b),(a,b)是a和b的最大公约数
金圭子同学的答案完全正确

[广告] 《精忠报国岳飞传完整版》火热发布