UVA 1393 - Highways (容斥原理計數)

題目鏈接：1393 - Highways

題意：給定一個n * m的點陣，問兩兩相連後，能組成多少條至少穿過兩個點的直線，並且不是水平或垂直的 思路：找過兩點的線段，由於是整數坐標，只要他的斜率不是整數，即x / y不是整數就能滿足答案，然後先記錄下這所有的位置，然後利用容斥原理求出對應每個點可以連出多少條這樣的線段，最後去求和，求和的時候要注意，由於有一些是重復計算了，比如1 1 和 2 2 連，2 2 和 3 3 連，這樣其實是算一條的，所以最後在求和的時候要扣掉重復的部分，直接減去sum[i / 2][j / 2]即可，因為會重復的肯定來自縮小兩倍後仍然存在的直線 代碼：

#include 
#include 

int n, m;
long long dp[305][305], ans[305][305];

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

int main() {
	for (int i = 1; i <= 300; i++)
		for (int j = 1; j <= 300; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (gcd(i, j) == 1);
	for (int i = 1; i <= 300; i++)
		for (int j = 1; j <= 300; j++)
			ans[i][j] = ans[i - 1][j] + ans[i][j - 1] - ans[i - 1][j - 1] + dp[i][j] - dp[i / 2][j / 2];
	while (~scanf("%d%d", &n, &m) && n || m) {
		printf("%lld\n", ans[n - 1][m - 1] * 2);
 	}
	return 0;
}