Halloween treats (PKU 3370)

http://poj.org/problem?id=3370

問題

要素数nの数列Aがある。Aの部分集合でcの倍数となっているものを一つ答えよ。
1<=c<=n<=100,000
1<=ai<=100,000

解法

常に解が存在することを示す。
a1を使用した場合S1=a1%cの値が作れる。a1,...,akの値を使用している時に、ak+1のを使用するとSk+1=(a1+...+ak+1)%cが作れる。この時、Sk+1=Siとなるようなi(1<=i<=k)が存在すると、Sk+1-Si=0となるので、i+1からk+1まで使うのが解となる。解が見つからないままSnまで行くと鳩の巣原理より、いままでのいずれかの値と被るので解は常に存在する。
なので、上記の証明をプログラム上で再現してやれば答えが出る。