所持金の最大値が1010円であることから酒の値段は1円から1010円まで可能性がありそうです。これらを全て試すわけにはいかないので、適切な価格設定を上手く見つけたいです。
酒の値段をX、席料をYとすると、客の所持金は A=kX+Y と表せます。
昇順ソートした 客i+1 と 客i の所持金を引いてみると di=Ai+1−Ai=(ki+1−ki)X となり、酒の値段は d1,...,dN−1 の公約数にするのが良いと分かります。
d1,...,dN−1 の公約数をGとし、Xの値段としてj番目の公約数を選ぶと席料は Gjmin(A) 通り選べるので、それらの合計が答えとなります。