很有意思的一个组合数学题。
整个题的最核心的思想就是，两个线段共线的判断！只要有两个点就可以确定一条线段（直线），那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了！所以两种算法的思想都在于一个2
第一种方法：最纠结的问题还是在于，怎么去重。想到了枚举角度的方法却没有想到怎么去重，还是思维不行。第一种方法是每次枚举所有可能的矩形，然后计算对角线的数量，这个很好算也就是有多少个矩形，直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况，这种情况一定说明这种对角线的角度第一次出现（因为我们从小到大枚举i和j），所以对答案贡献为正，还有一种情况是gcd(i,j)==2，这说明之前已经出现过了这种对角线，所以这里要减去对应的数量，注意这里是最重要的：减去的是对应的数量，然后其他的gcd值不用+也不用-。原因就在于，如果你有一个4*4的或者3*3的矩形对角线重算了，那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线！因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”