好久不写了啊，最近打算重新启用这个blog。就先写这个题目吧，满经典的。
【题目大意】
m * n的区域内，每个整数坐标都有整点，问以这些整点为端点能够形成多少个三角形。（0 < m, n <= 1000）
【题目分析】
这个题目乍一看挺简单的，但是想做对还是要仔细的思考下的。补集转化的思想，求出所有共线的三元组，然后用总数减掉就是答案了，关键就是如何求共线三元组。x坐标相同和y坐标相同的比较好计算，在一条斜线的就不好算了，画个图发现，即使斜率相同的线，经过的格点数可能各不相同。思路当然还是枚举y / x（不同的y / x确定了不同的矩形区域），之后如何有效的计算，我采用的方法可能有些麻烦，有点类容斥的方法。以斜率为a / b为例，(a, b) = g，那么m * n的区域内一定有(m - a + 1) * (n - b + 1)个那么大的矩形，这样的矩形经过的格点数是(g + 1)；然后因为同等斜率小一点的矩形(a - a / g, b - b / g)也是存在的，个数同样可以统计出来，但是有些大矩形包括了，要去掉；因此就采用这种思想，先求出大矩形的个数，然后依次往下减，就可以避免重复计数了。虽然这样复杂度有点高，不过极限数据还是比较快的跑出来了。
说的可能不太清楚，具体代码如下：
1 #include <cstdio>
2 #include <iostream>
3 using namespace std;
4 const int N = 1024;
5
6 bool tag[N][N];
7 long long calc(long long n)
8 {
9 if (n <= 2)
10 return 0;
11 return n * (n - 1) * (n - 2) / 6;
12 }
13 int gcd(int a, int b)
14 {
15 return b == 0 ? a : gcd(b, a % b);
16 }
17
18 int main()
19 {
20 int m, n, g, a, b, timer = 1, cnt[N], ta, tb;
21 long long ans;
22
23 while (scanf("%d %d", &m, &n) == 2)
24 {
25 memset(tag, 0, sizeof(tag));
26 if (m == 0 && n == 0)
27 break;
28 ans = calc((m + 1) * (n + 1)) - calc(m + 1) * (n + 1) - calc(n + 1) * (m + 1);
29 for (int i = m; i >= 1; i--)
30 for (int j = n; j >= 1; j--)
31 {
32 g = gcd(i, j);
33 a = i / g, b = j / g;
34 if (tag[a][b]) continue;
35 memset(cnt, 0, sizeof(cnt));
36 tag[a][b] = 1;
37 a = i, b = j;
38 ta = i / g, tb = j / g;
39 for (int k = g; k >= 2; k--)
40 {
41 cnt[k] += (m - a + 1) * (n - b + 1);
42 ans -= calc(k + 1) * cnt[k] * 2;
43 for (int t = 1; t <= k - 2; t++)
44 cnt[k-t] -= (t + 1) * cnt[k];
45 a -= ta, b -= tb;
46 }
47 }
48 cout << "Case " << timer++ << ": " << ans << endl;
49 }
50
51 return 0;
52 }
53