はまやんはまやんはまやん

hamayanhamayan's blog

Integer Coords [CSAcademy #68 B]

https://csacademy.com/contest/round-68/task/integer-coords/

x座標が[0,N]、y座標が[0,M]の(N+1)*(M+1)個の点がある。
任意の2点を選択し、それらを結んだ線分にK点含まれる場合の数を答えよ。

解法

任意の二点を全探索する。
以下のコードのようにループを回すと「点Aと点B」、「点Bと点A」のように同じペアを順番を変えて数え上げてしまうため、最後に答えを半分にする。
ある2点を結ぶ線分の中で座標がどちらも整数となる点の数を高速に数え上げれば答えとなる。
これには最大公約数を使おう。
二点のx座標の差をdx, y座標の差をdy、差のGCD(最大公約数)をgcとする。
すると、傾きはdy/dxであり、約分すると(dy/gc)/(dx/gc)となる。
約分済みの傾きをb/aとすると、x座標が+aされるとy座標が+bされる。
この間で座標がどちらも整数となる点は無く、+a,+bされた後の点はどちらも整数となる点になっている。
x座標のみで考えて見ると、dx/aだけこの移動が繰り返される。
よって、(dx/a+1)個、つまり(dx/(dx/gc) + 1)個の座標がどちらも整数の点が存在すると言える。
これがKである数をカウントして、半分にして答える。

int N, M, K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K;

    int ans = 0;
    rep(x1, 0, N + 1) rep(x2, 0, N + 1) rep(y1, 0, M + 1) rep(y2, 0, M + 1) {
        if (x1 != x2 or y1 != y2) {

            int dx = abs(x1 - x2);
            int dy = abs(y1 - y2);
            int gc = gcd(dx, dy);
            int cnt;

            if (dx == 0) cnt = dy + 1;
            else if (dy == 0) cnt = dx + 1;
            else cnt = dx / (dx / gc) + 1;
            if (cnt == K) ans++;
        }
    }
    cout << ans/2 << endl;
}