yukicoder 1358 語るなら枚数を...
解説の本質部分をまとめました
まず, $ H \leq K \leq Nとしても一般性を失わない. すると$ min(\lfloor \frac{Y}{N} \rfloor, \lfloor \frac{Y}{K} \rfloor, \lfloor \frac{Y}{H} \rfloor) = \lfloor \frac{Y}{N} \rfloorとなるのでN道のCDについて買う枚数を固定することを考える.
問題は$ Nx + Ky + Hz = Yなる非負整数$ (x,y,z)の組の個数を求める問題に帰着される. 先ほど述べた通り$ xを固定する. すると$ Ky + Hz = Y - Nxと変形できる. ここで$ 0 \leq y, zの条件を一旦無視して考える. $ Y - Nx = T, gcd(K, H) = gとおく. $ g \mid Tでないとき, 必ず整数解が存在しないことは示せる. よってその場合は無視し, 以後$ g \mid Tとして考えてよい. このとき$ K = gA, H = gB, T = gCと表すことができ, 方程式は$ Ay + Bz = Cとなる.
$ g = gcd(K, H)なので$ A,Bは互いに素, よって$ Ap + Bq = 1なる整数解$ (p, q)は必ず存在する. これは拡張ユーグリッドの互除法を用いて求めることができる.
ここで$ A(Cp) + B(Cq) = C, $ Ay + Bz = Cなので$ A(y - Cp) = -B(z - Cq)が成り立つ.
$ A, Bは互いに素なのである整数$ kを用いて$ y = kB + Cp, z = -kA + Cqと表せる. ここで$ 0 \leq y, zの条件を加味して考えると$ -\frac{Cp}{B} \leq k \leq \frac{Cq}{A}となる. この条件を満たす$ kを用いた$ (y,z)は方程式を必ず満たすので, あとはこれを満たす整数$ kの個数を求めればよい. これは$ \lfloor \frac{Cq}{A} \rfloor - \lceil -\frac{Cp}{B} \rceil + 1を計算することにより求められる.
以上より, 拡張ユーグリッドの互除法で$ (p,q)を求めるパートは前計算できるので, $ O(T \max (\lfloor \frac{Y}{N} \rfloor, \log H))でこの問題を解くことができた.