轩辕春秋文化论坛 - Powered by Discuz! Board

标题: 小学生问题,是不是难了点? [打印本页]

作者: KYOKO 时间: 2006-8-5 22:20 标题: 小学生问题,是不是难了点?

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

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

作者: 金圭子 时间: 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 时间: 2006-8-6 03:34 标题: 回复 #1 KYOKO 的帖子

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

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

分解质因数: 2647398563758362810978379

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

作者: nncaojian 时间: 2006-8-7 03:09

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

作者: KYOKO 时间: 2006-8-7 12:22

原题就是证明答案是

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

欢迎光临轩辕春秋文化论坛 (http://xycq.org.cn/forum/)