问题描述: 边长为m的正方形能否可以被边长分别为x,y的矩形地板不留缝隙地铺满?

数据范围 :m,x,y均在int范围

输入:
第一行测试案例个数n,
接下来n行每行三个参数参数——正方形边长m,矩形的长x和宽y

输出:
n行,每行一个结果——正方形能够被铺满输出yes,否则输出no

样例输入:

4
20 4 5
100 25 8
60 12 18
600 12 50

样例输出:

yes
no
no
yes

就是自己看了感觉这题挺有意思的,关键是证明部分哪里
个人认为这题的解题过程并不是主要的,关键是思考,理解和证明过程,特别是证明部分

先不给提示了,如果要说一句就是知道方法后有种原来这么……的感觉~

PS:从大神的角度来看这题或者不值一提,不过我感觉这题其实我给个100分也不过分的,但这只是证明过程值100分,解题过程还是笑笑算啦所以还是正常20分可以了~

[此贴子已经被作者于2018-1-4 07:51编辑过]

什么~说明白一点就是可以横铺和竖铺两种情况~
哇~这题其实感觉更像一道数学证明题~不知道发在编程领域会有什么反应~难怪没有人理会呢~

老大，你在刷贴么？

算啦,有种这贴要报废的感觉,毕竟课本上是不会怎么讲这些题的,就是感觉这题挺有意思才发~

是不是正方形的边长是矩形2个边长的公约数？

是两个矩形的其中一个公倍数,有意思的是矩形横着放和竖着放的组合最终能成立这样可以转化为全部横着放或者全部竖着放的~

[此贴子已经被作者于2018-1-4 18:06编辑过]

密铺关键是不留缝隙~也就是说明正方形的边长包含了a个竖着铺的和b个横着铺的,结合题意设正方形边长为m,矩形的长和宽分别为x和y,这样就有m=ax+by;
~

[此贴子已经被作者于2018-1-4 18:11编辑过]

主要是不知道你说的“特别是证明部分”是想证明什么？
是想证明 puts( m%x==0 && m%y==0 ? "yes" : "no" ); 吗？

先假设可能既有横铺又有竖铺，则 ax+by = cx+dy
变形为 (a-c)x = (d-b)y
可见可以将这方向不同的几块木板旋转180度以便与其它木板方向相同。（虽然用的是公式，但画图的话，一眼就能看出来）
总结一下就是，假如既有横铺又有竖铺时可以铺满正方形的话，那么一定存在一个全用横铺就可以铺满正方形的方案；假如不存在一个全用横铺就可以铺满正方形的方案，那么也一定不存在既用横铺又用竖铺就可能铺满正方形的方案。

对了,就是这个,你说得已经很详尽了,我感觉不必要再把你说的再重复一次了
这个我弄了很久才发现这个结论,一开始还打算用编程对铺地板进行穷举所有可能,但后来发现结论就这么简单,这个数学证明我自己也要消化一下才行~

我思考了一下题目关键是正方形,如果横铺和竖铺同时存在的话横铺所占的长度必然是竖铺的倍数,同样竖铺所占的长度必然是横铺所占的倍数,于是竖铺那部分可以全部用横铺来代替或者横铺那部分可以全部用竖铺来代替~

[此贴子已经被作者于2018-1-5 10:56编辑过]