好久不寫了啊，最近打算重新啟用這個(gè)blog。就先寫這個(gè)題目吧，滿經(jīng)典的。
【題目大意】
m * n的區(qū)域內(nèi)，每個(gè)整數(shù)坐標(biāo)都有整點(diǎn)，問以這些整點(diǎn)為端點(diǎn)能夠形成多少個(gè)三角形。（0 < m, n <= 1000）
【題目分析】
這個(gè)題目乍一看挺簡單的，但是想做對還是要仔細(xì)的思考下的。補(bǔ)集轉(zhuǎn)化的思想，求出所有共線的三元組，然后用總數(shù)減掉就是答案了，關(guān)鍵就是如何求共線三元組。x坐標(biāo)相同和y坐標(biāo)相同的比較好計(jì)算，在一條斜線的就不好算了，畫個(gè)圖發(fā)現(xiàn)，即使斜率相同的線，經(jīng)過的格點(diǎn)數(shù)可能各不相同。思路當(dāng)然還是枚舉y / x（不同的y / x確定了不同的矩形區(qū)域），之后如何有效的計(jì)算，我采用的方法可能有些麻煩，有點(diǎn)類容斥的方法。以斜率為a / b為例，(a, b) = g，那么m * n的區(qū)域內(nèi)一定有(m - a + 1) * (n - b + 1)個(gè)那么大的矩形，這樣的矩形經(jīng)過的格點(diǎn)數(shù)是(g + 1)；然后因?yàn)橥刃甭市∫稽c(diǎn)的矩形(a - a / g, b - b / g)也是存在的，個(gè)數(shù)同樣可以統(tǒng)計(jì)出來，但是有些大矩形包括了，要去掉；因此就采用這種思想，先求出大矩形的個(gè)數(shù)，然后依次往下減，就可以避免重復(fù)計(jì)數(shù)了。雖然這樣復(fù)雜度有點(diǎn)高，不過極限數(shù)據(jù)還是比較快的跑出來了。
說的可能不太清楚，具體代碼如下：
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