Mister雑記

競プロやります。

ARC102-C 「Triangular Relationship」 (300)

問題リンク

概要

 N以下の整数の組 (a, b, c)で、 a + b,  b + c,  c + aが全て Kの倍数であるものの個数を求めよ。

制約

  •  1 \leq N, K \leq 2 \times 10^5

解説

 a' = a \% Kとおく。 b', c'も同様。

このとき (a + b) \% K = 0 \Leftrightarrow (a' + b') \% K = 0となる。

ここで a'の値について場合分けをする。


1.  a' = 0の場合

 (a' + b') \% K = 0より、まず a' + b' = 0とすると b' = 0となる。

一方 0 \leq b' \lt Kより a' + b' \geq Kは成立しないため、これが唯一の解となる。

同様にして c' = 0となり、これは (c' + a') \% K = 0に矛盾しないため条件を満たす。

まとめると a' = b' = c' = 0は条件を満たす。これは元に戻すと「 a, b, cが全て Kの倍数」となる。

2.  a' \gt 0の場合

 (a' + b') \% K = 0 0 \leq b' \lt Kから、 a' + b' = Kのみが成立。よって b' = K - a'となる。

同様にして c' = K - b' = a'となる。

ここで (c' + a') \% K = 2a' \% K = 0が成立する条件を考える。

まず Kが奇数の場合は 0 \lt a' \lt Kにて常に 2a' \% K \gt 0より不成立。

次に Kが偶数の場合。これは a' = K / 2のみにて 2a' \% K = 0が成立する。

まとめると、 Kが偶数の場合のみ a' = b' = c' = K / 2が条件を満たす。


以上で全パターンが網羅できた。ではパターン数を数えてみよう。

まず a' = b' = c' = 0 1 \sim Nには Kの倍数が \lceil N / K \rceil個含まれているため、 各 a, b, cについてそこから1つずつ自由に選ぶことを考えるとパターン数は {\lceil N / K \rceil}^3通り。

次に Kが偶数の場合限定で a' = b' = c' = K / 2 1 \sim Nには Kで割って K/2余る値が \lceil (N + K/2) / K \rceil個含まれているため、 先と同様に考えてそのパターン数は {\lceil (N + K/2) / K \rceil}^3通り。

ここでうっかり {\lceil N / (K / 2) \rceil}^3通りとしないように。 たとえば (a', b', c') = (0, 0, K / 2)なんかは条件を満たす組ではない。

実装例

#include <iostream>
using namespace std;
using ll = long long;

ll triple(ll a) {
    return a * a * a;
}

int main() {
    ll N, K;
    cin >> N >> K;
    ll ans = triple(N / K);
    if (K % 2 == 0) {
        ans += triple((N + K / 2) / K);
    }
    cout << ans << endl;
    return 0;
}

まぁ実装に関しては何も言うことはない。

感想

  • 冷静に考察を積みましょう。
    • 本番の私は上と全く同じ考察をして通したので(6分かかった)。
  • Twitterで「A~Cまでループ構文が要らないコンテスト」と言われていたのは面白かった。
    • それでいてDがクソ難しかっただけに、数学が得意な人にはチャンスだったと言える。