B - Share It Now

この問題は剰余を問います。

$J_i:=$ 宝石 $i$ の個数 $(1\le i\le M)$ とします。
宝石 $i$ を $S$ 人全員で同じ量ずつ配ることができるのは $J_i\ mod\ S=0$ となるときです。なお $x\ mod\ y$ は $x$ を $y$ で割ったあまりを表します。

$J_i\ mod\ S\neq 0$ のとき、$S$ 人全員で同じ量ずつ分け合うために必要な宝石 $i$ の個数 $E_i$ は $S-(J_i\ mod\ S)$ 個です。これが正しいことは、あまりの性質を用いて示すことができます。一方 $J_i\ mod\ S= 0$ のとき、明らかに $S$ 人で配り切れるので、$E_i=0$ とするのが適切です。

また答えが equality となる条件は、すべての $i$ に対し $E_i=0$ が成り立つことであることも明らかです。

以上からこの問題は $O(N\max (L_i)+M)$ で解くことが可能です。以下、解答例(C++,Python)です。