[1] Alice が勝てる盤面の特徴づけ

はじめの石の個数を \(n\) としたとき、\(n,A,B\) がどのような関係を満たすときに Alice が勝てるかを分析しましょう。

\(n <A\) のときは、明らかに Alice の負けです。以下、\(n\geq A\) とします。

ここで、以下の重要な事実に気付く必要があります。

• Alice は石を取れるだけ取るのが最適な行動である。

以上より、Alice が勝つ必要十分条件は

• \(n\geq A\) かつ \(n\bmod A <B\)

であることが分かりました。

[2] 解の計算

[1]で整理した条件を満たす \(n\) を数え上げましょう。

\(n\bmod A<B\) と \(1 \leq n \leq X\) をともに満たす \(n\) の個数を \(f(X)\) とします。

このとき、答えは \(A\) 以上 \(N\) 以下で \(n\bmod A<B\) を満たす \(n\) の個数なので、\(A\leq N\) の場合 \(f(X)\) を用いて \(f(N) - f(A-1)\) と表せます。\(A>N\) の場合答えは \(0\) です。

\(f(X)\) は \(X \bmod A\) が \(1,2,\ldots,A-1, 0,1,2,\ldots,\) と周期的になっていることを利用すると、以下の式で求められます。

\[ f(X)=\Big\lfloor \frac{X}{A}\Big\rfloor \mathrm{min}(A, B) +\mathrm{min}(X \bmod A, B-1)\]

\(f(X)\) の計算は \(O(1)\) で出来るので、この問題を \(O(1)\) で解くことが出来ました。

[3] 実装例

Python:

n, a, b = map(int, input().split())

def f(x):
    return x // a * min(a, b) + min(x % a, b - 1)

print(max(f(n) - f(a - 1), 0))