この解説では，以下のステップで紹介します。
1. 愚直な解法
2. 想定解法
3. チャレンジ：さらに高速な解法

前提

解説の都合上，制約の「合計 \(9999\) 枚以下の硬貨でちょうど \(N\) 円を支払うことができる」という記述の \(9999\) を \(P\) と読み変えた問題について解説します。

1. 愚直な解法

この問題は \(Ax + By + Cz = N\) となる \((x,y,z)\) の組のうち，\(x+y+z\) が最小となる場合の値の組を求める問題です。
合計で \(P\) 枚以下で支払うことができるという制約から，以下のような解法が浮かびます。

• \(0 \leq x, y, z \leq P\) の範囲の \(x, y, z\) を全探索する。

これは，以下のようなコードで求めることができます。

ans = P + 1
for x in range(P + 1):
    for y in range(P + 1):
        for z in range(P + 1):
            if x * a + y * b + z * c != N:
                continue
            if ans > x + y + z:
                ans = x + y + z

しかし，この解法は \(P\) 回のループを \(3\) 重で実行しているため，\(O(P^3)\) となってしまいます。
\(P=10000\) とすると，計算回数は \(10^{12}\) 程度となります。この計算回数の実行には約 10 分ほどかかってしまい，実行時間制限の 2 秒には到底間に合いません。
次のステップでは，この計算を高速化することを考えます。

※ \(O(\dots)\) という表記は計算量を示します。計算量のことが分からない場合は APG4b の記事 をご覧ください。

2. 想定解法

ステップ 1 の \(O(P^3)\) を高速化することを考えましょう。
突然ですが， \((x, y)\) の値を固定した場合，\(z\) の値はどのようにして求めることができるでしょうか？
ステップ 1 のように \(0 \leq z \leq P\) の範囲の \(z\) を全探索するよりも高速な手段があります。

まず，\(N-Ax-By\) が \(C\) で割り切れない場合や \(Ax+By>N\) となる場合は，条件を満たす \(z\) の値は存在しません。

逆に \(N-Ax-By\) を \(C\) で割り切れて，\(Ax+By\leq N\) を満たす場合は，\(Cz = N - Ax - By\) すなわち \(z = \frac{N - Ax - By}{C}\) と求められます。

以上の解法の場合，\(x, y\) を \(0 \leq x, y \leq P\) の範囲で全探索することで求めることができます。以下のようなコードで求めることができます。

ans = P + 1
for x in range(P + 1):
    for y in range(P + 1):
        tmp = x * a + y * b
        if tmp % c != 0 or tmp > n:
            continue
        z = (n - tmp) // c
        if ans > x + y + z:
            ans = x + y + z

Python (PyPy3) の AC コードはこちら
C++ の AC コードはこちら

この解法では \(O(P^2)\) となり，\(P=10000\) のとき計算回数は \(10^8\) 回程度と，高速な言語では 1 秒程度で求めることができます。

Python を利用する場合には，言語で「Python (PyPy)」を選択すると，このようなコードでは高速に実行することができます。（『どのようなコードでも CPython より PyPy のほうが実行速度が速い』というわけではありません）

3. さらに高速な解法

\(P \leq 9999\) の制約下では \(O(P^2)\) で十分高速ですが，\(O(P \log \min(A,B,C))\) や \(O(P + \log \min(A,B,C))\) の解も存在します。

まず、\(x\) の値を最初に決めてしまいましょう。\(x\) の値が定まっている場合、\(By+Cz=N-Ax\) かつ \(y,z\geq 0\) となる \(y,z\) 全体にわたって、\(y+z\) の最小値が求まればよいです。

この \(By+Cz=N-Ax\) という形の方程式は、拡張ユークリッドの互除法を用いて \(O(\log \min(B,C))\) で一般解を求めることができます。一般解のうち、\(y,z\geq 0\) を満たすときの \(y+z\) の最小値は簡単に求まるので、ありうる \(x\) についてそれぞれこれを解けば良いです。対称性より、枚数を固定する硬貨を適切に定めれば、計算量が \(O(P\log\min(A,B,C))\) になります。

これに加えて、ある工夫を加えることで、計算量をさらに改善することができます。 方程式 \(By+Cz=\gcd(B, C)\) の一般解を最初に求めておくことにして、\(x\) を決めた後は、この一般解を \(\frac{N-Ax}{\gcd(B,C)}\) 倍すれば、\(By+Cz=N-Ax\) の解が \(O(1)\) で求まります。なお、\(N-Ax\) が \(\gcd(B,C)\) で割れない場合は、解が存在しないことが簡単に示せます。このように、先に一般解を求めておいてそれを利用して計算すれば、計算量を \(O(P+\log\min(A,B,C))\) まで改善できます。