居酒屋

所持金の最大値が$10^{10}$円であることから酒の値段は$1$円から$10^{10}$円まで可能性がありそうです。これらを全て試すわけにはいかないので、適切な価格設定を上手く見つけたいです。 酒の値段をX、席料をYとすると、客の所持金は $A = kX + Y$ と表せます。 昇順ソートした $客_{i+1}$ と $客_i$ の所持金を引いてみると $d_i = A_{i+1} - A_i = (k_{i+1} - k_i)X$ となり、酒の値段は $d_1, ..., d_{N-1}$ の公約数にするのが良いと分かります。 $d_1, ..., d_{N-1}$ の公約数を$G$とし、Xの値段としてj番目の公約数を選ぶと席料は $\frac{min(A)}{G_j}$ 通り選べるので、それらの合計が答えとなります。