ACM 进阶学习第一课----简单数学问题之同余相关（1）前言在ACM竞赛中,经常可以看到数学问题的身影，可以是纯
ACM 进阶学习第一课----简单数学问题之同余相关（1）
前言
在ACM竞赛中,经常可以看到数学问题的身影，可以是纯数学问题,也可以是需要利用数学上的一些公式,定理,算法来辅助解决的问题。会者不难,而不会的选手在赛场上一般很难推出公式或进行证明，往往想起来费劲,写起来却很轻松。
常见的数学问题：
数论
组合数学
博弈论
线性代数
高等数学
线性规划
概率统计
...
关于数论
简而言之,数论就是研究整数的理论，在ACM竞赛中,经常用到数论的相关知识。纯数论的题目不多,大部分是和其他类型的问题结合起来的。约数,倍数,模线性方程,欧拉定理,素数。
数论的主要内容第一部分:同余相关
整除的性质->欧几里德算法
->扩展欧几里德算法->中国剩余定理
第二部分:素数相关
算术基本定理->欧拉定理
->素数测试-> Pollard rho方法
基本概念：
1、素数合数
如果大于1的正整数p仅有的正因子是1和p, 则称p为素数(prime)。
大于1又不是素数的正整数称为合数(compound)，如果n是合数, 则n必有一个小于或等于n1/2的素因子。
2、算数基本定理
·····每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的“乘积”可以有0个、1个或多个素因子）。
·····换句话说, 任意正整数n可以写成n=2a1*3a2*5a3*…,其中a1,a2,a3等为非负整数
·····这个定理也叫做惟一分解定理。它是一个定理而不是公理！虽然在大多人看来，它是“显然成立”的，但它的确是需要证明的定理
3、除法和同余
---令a为整数，d为正整数，那么有惟一的整数q和r，其中0≤r<d，使得a=dq+r
---可以用这个定理来定义除法：d叫除数，a叫被除数，q叫商，r叫余数。如果两个数a,b除以一个数c的余数相等，说a和b关于模c同余，记作a≡b(mod c)
本次先学习同余相关。同余相关
同余相关主要内容
整除的性质
欧几里德算法
扩展欧几里德算法
中国剩余定理整除的性质
若a|b, a|c, 则a|(b+c)若a|b, 那么对所有整数c, a|bc若a|b, b|c, 则a|c若a|b,b|a => a=±b
若a=kb±c => a,b的公因数与b,c的公因数完全相同整除关系具有传递性.整除显然有自反性和反对称性，所以它是一个偏序关系。(partial order), <|,Z>是一个格
FIR：最大公约数·最小公倍数最大公约数令a和b是不全为0的两个整数，能使d|a和d|b的最大整数称为a和b的最大公约数(greatest common divisor)
，用gcd(a,b)表示，或者记为(a,b)。显然满足以下性质：
·gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)
·gcd(a,0)=|a|
·gcd(a,ka)=|a|,k为任意整数·a,b互素,则gcd(a,b)=1
最小公倍数lcm
令a和b是不全为0的两个整数，能使a|d和b|d的最小整数称为a和b的最小公倍数，用lcm(a,b)表示，或者记为[a,b]
则有定理：ab=gcd(a,b)*lcm(a,b)即是：最小公倍数=两数的乘积/最大公约（因）数
证明如图：
明显已经证明。
实例测试【1】11年腾讯笔试题目给出一个数N，含数字1、2、3、4，把N的所有数字重新排列一下组成一个新数，使它是7的倍数。
【分析】把数字1、2、3、4从中抽出，然后把其他数字按照原顺序排列（事实上，怎么排列都无所谓）组成自然数w
w*10,000整除7取余有7种可能，即是为0、1、2、3、4、5、6。这时如果能用数字1、2、3、4排列出7个数，使它们整除7取余的值分别为0、1、2、3、4、5、6，把这个4位数接在w后面即为问题的解。
幸运的是，有这样的7个数，如下： 余数0（7）1 2 3 4 5 6 排列 32411324 1234 2341 1243 1342 2134 选取某一个排列作为后缀时，若w×10000模7余d，则选取（7-d）为余数的那个排列即是W可用表达式：W=d + 7 * m, 而后四位的排列则可用L=（7-d） + 7 * n,即是L+W = 7 + 7*（m+n），即是7的倍数 。
参考代码如下：
【未完待续】。。。。
