完美矩形题解
一个结论，a * b的矩形的对角线切割的方格数=gcd(a,b) * (a/gcd(a,b)+b/gcd(a,b)-1)
原因是这样的，当gcd(p,q)=1时，p*q的矩形的对角线，除了起点和终点，不会经过任何整点。
在这条对角线穿过一个方格边缘的时候，切割的方格数会加一。
可以穿过的边缘=p-1+q-1
由于出发时的格子也会被切割，所以总切割方格数为p+q-1
回到原来的结论，我们可以枚举gcd(a,b)，把问题变成寻找互质的p和q使得切割方格数为n/gcd(a,b)
2021-04-11 21:16 已编辑 西北农林科技大学
关注
全部评论
相关推荐
投递华为等公司10个岗位 > 点赞 评论 收藏
转发