剩余系

先放资料。 前置技能点： # 剩余系 剩余系**:设模为m,则根据余数可将所有的整数分成m类，分别记成[0],[1],[2],…[m-1]****，**

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

昨天那道签到的数学题没搞出来不开心. 是时候刷一波数学了 这题题意是说，从n个数中任选m个，使得m个的和为c的倍数. 如果有解，输出选的数的下标，否则输出无解字符串. 抽屉原理的原始描述是，如果有n+1个物品，有n个抽屉，那么至少有一个抽屉有2个物品.