剩余类和完全剩余系（简单理解）

2019-04-13 13:00发布

站内文章 / 模拟电子
14122 0 1676
最近刚刚学了剩余类和完全剩余系，进行了简单的总结，如果理解错误，欢迎大牛指出！！
剩余类和完全剩余系：
定义1：取定m>0，任意的r∈Z，设r  mod m ={qm+r|q=0，±1，±2，.....} 把r  mod  m  称为模m的一个剩余类，除以m后余数相等的记为一类，同余同类，不同于不同类。(只要取定一个m，那么就可以将所有的整数分为m个剩余类，任意的r只要是对m取模相同，则在同一个剩余类里面)
定理1   取定m>0，则 1）任意的a∈Z，a恰在模m的一个剩余类 r  mod  m，r=0,1,2，....m-1中。（即将所有整数分为m份，放入不同的剩余类中） 2）任意的x，y∈Z，x，y在模m的同一个剩余类（x≡y mod m）   特点：由定理1，给定模m， ·任意r，s∈Z,  r mod m =s mod m或 r mod m ∩ s mod m ＝ ∅
 ·恰有 m 个不同的模m的剩余类 0 mod m，1 mod m......（m-1） mod m。 ·Z=∑ i mod m  i∈【0，m-1】。
例子： 设S={a1，a2,....an}，其中ai都是整数，证明存在S的一个非空子集，其各个元素的和被n整除。 证：（运用了鹊巢原理）考虑n个整数 S1=a1，S2=a1+a2,...... , Sn=a1+a2+...an,若Si被n整除，则Si符合，若没有是 被n整除（即Si∉0 mod n），那么S1,S2,....,Sn 中必有两数在模 n 的同一个剩余类中，那么这两数只差就是n的倍数。 不妨设 Si≡Sj（mod n），i

定义2：一组数a0,a1,.....,am-1 称为模m 的一个完全剩余系，如果 ai∈i mod m,i=0,1,2,...,m-1。(因为完全剩余系里面两两各不相同) 设 a1,a2,...,am 是模m的一个完全剩余系，则 ·如果 ai≡aj（mod m）, 就有 i=j，ai=aj 。
常用的完全剩余系 ·0,1，.....，m-1称为模m的非负最小完全剩余系 · m 为奇数时，  -(m-1)/2 , -(m+1)/2 , ... , -1 , 0 , 1 , ... , (m-1)/2 · m为偶数时， ① -m/2, -m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1 ②-m/2+1 , ... , -1 , 0 , 1 , ... , m/2-1 , m/2 称为模m 的绝对最小完全剩余系。

完全剩余系的判定及构造： 定理2 一组数a1，a2 , ... , ak 是模m的一个完全剩余系 {k=m                                                } {a1 , a2 , ... , ak对模m两两互不同余}
定理3 若a1 , a2 , ... ,am 是模m的一个完全剩余系， 则ka1, ka2,...,kam 也是模 m的一个完全剩余系。
定理4 设（k，m）=1，b∈Z， 若a1,a2, ... , am 是模m的一个完全剩余系，则  ka1+b , ka2+b , ... , kam+b（运用了定理3，然后都加上b相当于同时全部元素移动了b步） 也是模m的一个完全剩余系。
定理5 设（m1，m2）=1，若x1,x2分别通过模m1，m2的一个完全剩余系，则m1x2+m2x1通过模m1m2的一个完全剩余系。 证：(m1x2+m2x1)%m1m2=x2%m2+x1%m1




附上一道acm题： Candy Distribution Time Limit:1000MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Submit Status Description N children standing in circle who are numbered 1 through N clockwise are waiting their candies. Their teacher distributes the candies by in the following way: First the teacher gives child No.1 and No.2 a candy each. Then he walks clockwise along the circle, skipping one child (child No.3) and giving the next one (child No.4) a candy. And then he goes on his walk, skipping two children (child No.5 and No.6) and giving the next one (child No.7) a candy. And so on. Now you have to tell the teacher whether all the children will get at least one candy? Input The input consists of several data sets, each containing a positive integer N (2 ≤ N ≤ 1,000,000,000). Output For each data set the output should be either "YES" or "NO". Sample Input 2 3 4 Sample Output YES NO YES

题解是转载别人博客里的。网址：http://blog.csdn.net/tsaid/article/details/7385406
题意：老师给N个学生发糖，第x次发糖发给编号为 f(x) 的学生。可以推知：f(x) = x * (x+1) / 2 % N（学生号为 0, 1, 2, 3, ```N-1 ） 现在问你是否每个学生都能得到至少一颗糖。 题解：要使每个学生都至少得到一颗糖，那么f(x) 应该构成模N的完全剩余系。 那么这个问题的反面就是在什么情况下，f(x) 不能构成模N的完全剩余系。 我们知道若存在 x != y, 使得 f(x) = f(y)，那么f(x)边不能构成模N的完全剩余系。 若f(x)  = f(y)， 推出 x * (x+1) / 2 % N = y * (y+1) / 2 % N,  推出 (x+y+1)(x-y) / 2 = 0 % N 这样可以假设 N^t = (x+y+1)(x-y)/2，于是这个等式成立的条件便是f(x) = f(y)成立的条件。 下面我们具体分析： 首先给出两个显而易见的结论： (1).任意一个偶数都可以表示成 b * 2^e 的形式（b为奇数） (2).(x+y+1)与(x-y)中必定一个是偶数一个是奇数
假如 N^t = (x+y+1)(x-y)/2 1.若N是奇数，那么N^t 还是奇数，于是我们一定可以找到适当的x,y,t使得 (x+y+1)(x-y)/2 = N^t，例如令 x = y + 2， 得 y + 3 = N^t， 得 y = N^t - 3。 所以在这种情况下f(x)  = f(y)，不能构成完全剩余系。 2.若N是2的幂，令N=2^e,  那么N^t = 2^(e*t) 为偶数，而(x+y+1)(x-y)/2是奇数，显然不可能存在x,y,t使得 N^t = (x+y+1)(x-y)/2。所以在这种情况下f(x)  != f(y) 可以构成完全剩余系。 3.若N是形如 b * 2^e 的偶数，那么 N^t = b^t * 2^(e*t)。  令(x+y+1) = b^t， (x-y)/2 = 2^(e*t) 即(x+y+1) = b^t     //一式     (x-y) = 2^(e*t+1)   //二式 解一式二式构成的方程组，得到 2x = 2^(e*t+1) + b^t - 1，左右均为偶数，显然x是有解的，那么y也是有解的。所以在这种情况下f(x)  = f(y)，不能构成完全剩余系。 注意上面的式子并不是一般的式子，我们只是用它们来判断存在性，由 N^t = (x+y+1)(x-y)/2这一假设引出的，是由结果到原因的推导，并不能随意的求解。例如 2x = 2^(e*t+1) + b^t - 1，假如一边是奇数，一边是偶数，那么x显然是无解的。
#include int main() { int n; while ( scanf("%d",&n) != EOF ) { if ( n & ( n - 1 )) printf("NO "); //这个方式判断n是否是2的幂，还是蛮巧妙的。 else printf("YES "); } return 0; } //没想到那么短……
目前理解到这里= =... 

热门文章