完美矩形题解

一个结论，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)