UVa 1393

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4139

题意：

有一个n行m列（1≤n,m≤300）的点阵，问：一共有多少条非水平非竖直的直线至少穿过其中两个点？

分析：

不难发现两个方向是对称的，所以只统计“”型的，然后乘以2。
方法是枚举直线的包围盒大小a*b，然后计算出包围盒可以放的位置。
首先，当gcd(a,b)>1时肯定重复了。其次，如果放置位置不够靠左，也不够靠上，则它和它“左上方”的包围盒也重复了。
假定左上角坐标为(0,0)，则对于左上角在(x,y)的包围盒，其“左上方”的包围盒的左上角为(x-a,y-b)。
这个“左上角”合法的条件是x-a≥0且y-b≥0。包围盒本身不出界的条件是x+a≤m-1, y+b≤n-1，一共有(m-a)(n-b)个，
而“左上方”有包围盒的情况，即a≤x≤m-a-1且b≤y≤n-b-1，有c = max(0, m-2a) * max(0, n-2b)种放法。
相减得到：a*b的包围盒有(m-a)(n-b)-c种放法。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;

const int UP = 300 + 5;
int g[UP][UP];

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a%b);
}

int main() {
    for(int r = 1; r < UP; r++)
        for(int c = 1; c < UP; c++) g[r][c] = gcd(r,c);
    int n, m;
    while(scanf("%d%d", &n, &m) && n) {
        int ans = 0;
        for(int a = 1; a <= n; a++) {
            for(int b = 1; b <= m; b++) {
                if(g[a][b] != 1) continue;
                ans += (n-a) * (m-b) - max(n-a-a,0) * max(m-b-b,0);
            }
        }
        printf("%d
", ans*2);
    }
    return 0;
}