完美矩形题解
一个结论，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 已编辑 西北农林科技大学 C++
关注
全部评论
相关推荐
11-15 00:37
南京大学 FAE 经历了无数测评和宣讲会，拒信是一封又一封，努力却没有回应，真让我感到很累啊。似乎明白自己投了简历也会被刷，面试也毫无意义，渐渐开始懒得再投、再测、再面。求求了，给我一个offer，让我重新燃起斗志吧！
牛客84762733号：南✌，你不是没有offer，你是没有让你满意的offer，而身为双非鼠鼠的我，连面试都没有
点赞 评论 收藏
分享
CVTE公司福利 257人发布 点赞 评论 收藏
分享