http://poj.org/problem?id=2356
题意:有n个数,从中选取若干个(1..n),和能被n整除。问是否有解,无解输出0,有解的话,输出个数以及选择的ai
由抽屉原理可知一定有解: 做一个带模的前缀和 sum[i]=(sum[i-1]+a[i])%n n个数,sum[i]最多有n种。 如果某个sum[i]为0,那么表示从1到i的和能被n整除。 如果所有的sum[i]不为0,那么一共有n个sum[i],n-1个值(1..n-1),一定有sum[i]==sumj 那么a[i]到a[j]的和一定能被n整除。
阅读更多