先放资料。 前置技能点： 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，** 这m个数**{0,1,2,****…****m-1}**称为一个完全剩余系， 每个数称为相应类的代表元。 当m=10（偶数）时候，则{0,1,2,3,4,5,6,7,8,9}是最小非负完全剩余系 {-5,-4,-3,-2,-1,0,1,2,3,4,5} 是绝对值最小完全剩余系 {-4,-3,-2,-1,0,1,2,3,4,5} 绝对值最小 {1,2,3,4,5,6,7,8,9,10}是最小正完全剩余系 简化剩余系:在每个剩余类选取至1个与m …

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整除。 …

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说,从n个数中任选m个,使得m个的和为c的倍数. 如果有解,输出选的数的下标,否则输出无解字符串. 抽屉原理的原始描述是,如果有n+1个物品,有n个抽屉,那么至少有一个抽屉有2个物品. 由抽屉原理我们可以退出一个结论,对于任意 n个自然数,一定有连续的一段和为n的倍数. 证明如下: 　设这n个自然数分别为a1,a2,a3,a4....an 　处理一个前缀和sum[i] = (sum[i-1] + a[i])%n 　因为n的剩余类有n种,分别为0,1,2...n-1 　所以sum[1],sum[2],sum[3]..sum[n] 　那 …