yukicoder No.321 (P,Q)-サンタと街の子供たち

すごく好きなタイプの問題です。

問題

No.321 (P,Q)-サンタと街の子供たち - yukicoder

解法

a*P + b*Q は, P と Q の最大公約数 G に関して, c*G (c は整数) という整数値すべてを取ることはよく知られています。
今回も似たようなことが出来ますが, (c*G, d*G) (c, d は整数)を満たすすべての座標にいける, と言った単純なことは成り立ちません(一番最後の入力で間違ってることに気づく)。

なのでもうちょっと冷静に問題を見てみます。よく考えると, たどり着ける座標 x, y は,
x = a*P + b*Q
y = c*P + d*Q
と書けますが, この a, b, c, d の間に何らかの条件が成り立ちます。具体的には, a と d の偶奇が一致, b と c の偶奇が一致しなければなりません。x 座標で P 動かすと y 座標で Q 動かさないといけない, x 座標で Q 動かすと y 座標で P 動かさないといけない, という関係からこの偶奇性が出てきます。

ということで, a, b, c, d の値を求めましょう。拡張ユークリッドの互除法を用いて, G = x*X + y*Y であるとわかったとすると, 目標地点にたどり着くための a, b および c, d がひとつずつ求まります。
ただ, 例えば a, b の答えの組はこれだけではなく, a = a+Q/G, b = b-P/G としたものも, x 座標に関して座標を合わせる答えの一つになります。こんな感じで a, b, c, d の偶奇を調整して, a と d の偶奇が一致しかつ b と c の偶奇が一致するようなものがあれば良いわけです。

また, さきほど a, b の答えの組は一つではないと言いましたが, 実際には調べなければならない組は, 拡張ユークリッドの互除法を使って求めたものと, その答えを a = a+Q/G, b = b-P/G と調整したものの 2 組だけです。これは, 2 回以上 Q/G とかを使って調整しても, また偶奇が戻ってしまうことからわかります。

ということで, 各頂点に対して O(1) で到達判定ができるので AC 出来ます。

// extgcd
ll extgcd(ll a, ll b, ll& x, ll& y) {
    if (a < b) swap(a, b);
    ll d = a;
    if (b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    } else {
        x = 1; y = 0;
    }
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll P, Q, X, Y;
    cin >> P >> Q;
    ll G = extgcd(P, Q, X, Y);
    int N;
    cin >> N;
    int ans = 0;
    for (int i = 0; i < N; i++) {
        ll x, y;
        cin >> x >> y;
        if (G == 0) {
            if (x==0 && y==0) ans++;
            continue;
        }
        if (x%G!=0 || y%G!=0) continue;
        ll a = (x/G)*X, b = (x/G)*Y;
        ll c = (y/G)*X, d = (y/G)*Y;
        bool ok = false;
        for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
            ll na = a+j*(Q/G), nb = b-j*(P/G);
            ll nc = c+k*(Q/G), nd = d-k*(P/G);
            na = abs(na%2), nb = abs(nb%2);
            nc = abs(nc%2), nd = abs(nd%2);
            ok |= (na==nd && nb==nc);
        }
        if (ok) ans++;
    }
    cout << ans << endl;
    return 0;
}