poj 2356 Find a multiple (剩余类,抽屉原理)

 

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

题意:有n个数,从中选取若干个(1..n),和能被n整除。问是否有解,无解输出0,有解的话,输出个数以及选择的a[i]( 不是i)

由抽屉原理可知一定有解:
做一个带模的前缀和 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]==sum[j](i<=j)
那么a[i]到a[j]的和一定能被n整除。

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz