Codeforces 136D (220D) Little Elephant and Triangle

問題

(x, y)（0≦x≦w, 0≦y≦h）を満たす点3点からなる三角形で、
面積が正の整数であるものの個数を求めよ。

ただし、点の順序は区別するものとする。

制約条件

w, h≦4000

方針

(0, 0), (a, b), (c, d)を結んでできる三角形の面積は、|ad - bc| / 2.
これが整数になればよいので、
(x, y)が偶数、奇数かで点を分類して数えておいて、
それぞれのパリティごとに点の個数を掛け合わせればよい。

そのままだと面積が0の点も含んでしまうので、以下の場合にわけて取り除く。

• 1点または2点に縮退している場合
• y軸またはx軸に平行な直線上に三点が並ぶ場合
• 軸に平行でない直線上に三点が並ぶ場合

ソースコード

const int mod = (int)1e9 + 7;
int h, w;
ll cnt[2][2];
ll P(int n, int m){
	ll res = 1;
	rep(i, m) res = res * (n - i) % mod;
	return res;
}
ll tri(ll n){
	ll res = n;
	rep(i, 2) res = res * n % mod;
	return res;
}
int main(){
	cin >> h >> w;
	
	ll ans = 0;
	rep(i, h + 1) rep(j, w + 1){
		cnt[i % 2][j % 2]++;
		if(i && j){
			int c = __gcd(i, j);
			//3点が軸に平行でない一直線上にある場合
			//順番6通りを無視し、かつ下にいくものを数えていないので、本来は12倍
			//視点が(h - i + 1) * (w - i + 1)通り
			ans += mod - 12ll * (c - 1) * (h - i + 1) * (w - j + 1) % mod;
		}
	}
	ans += mod - (w + 1) * P(h + 1, 3) % mod; //縦にならぶ
	ans += mod - (h + 1) * P(w + 1, 3) % mod; //横にならぶ
	ans += P((h + 1ll) * (w + 1), 3) % mod; //こことこの下の行で、
	ans += mod - tri((w + 1ll) * (h + 1)); //一点か二点に縮退している場合
	
	rep(a, 2) rep(b, 2) rep(c, 2) rep(d, 2) rep(e, 2) rep(f, 2){
		int aa = c - a, bb = d - b;
		int cc = e - a, dd = f - b;
		
		//パリティが条件を満たしているなら数える
		if((aa * dd - bb * cc) % 2 == 0)
		ans += cnt[a][b] * cnt[c][d] % mod * cnt[e][f] % mod;
	}
	cout << ans % mod << endl;
	
	return 0;
}