ARC 185

A - mod M Game 2

解説 AC だが、かなり解像度が低い。

$\displaystyle \sum_{k=1}^{N} k = \frac{1}{2}N(N+1)$ より両者のカードの総和は $N(N+1)$。 最後の Bob の出す手が $b$ のとき Alice が最後に出した手までの総和は $N(N+1) - b$。 $N(N+1) - b$ が $0$ にできたら Bob の勝ち、それ以外のときは Alice の勝ち。

\begin{align} N(N+1) - b &\equiv 0 \mod M \\ N(N+1) &\equiv b \mod M \\ \end{align}

$b \in [1,N]$ より、$1 \leq (N(N+1) \mod M) \leq N$ のときは Bob の勝ち。それ以外のときは Alice の勝ち

void solve() {
    ll T;
    cin >> T;
    rep(_, T) {
        ll N, M;
        cin >> N >> M;

        ll x = N * (N + 1) % M;
        string ans = "Alice";
        if (clamp(x, 1LL, N) == x) {
            ans = "Bob";
        }
        cout << ans << endl;
    }
}