ACM 进阶学习第一课----简单数学问题之同余相关（1）

逃离我推掉我的手 2022-05-12 23:58 209阅读 0赞

# 前言 #

在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)**

即是：最小公倍数=两数的乘积/最大公约（因）数

证明如图：

![SouthEast][]

**明显已经证明。**

### 实例测试 ###

【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个数，如下：**

选取某一个排列作为后缀时，若w×10000模7余d，则选取（7-d）为余数的那个排列即是W可用表达式：W=d + 7 \* m, 而后四位的排列则可用L=（7-d） + 7 \* n,即是L+W = 7 + 7\*（m+n），即是7的倍数 。

**参考代码如下：**

/***** 简单数论题目 ********/
 
 /******** written by C_Shit_Hu ************/
 
 数论///
 
 /****************************************************************************/
 /* 
 把数字1，2，3，4从中各抽出1个，然后把其他数字按原顺序（其实任一顺序都可以）排列，组成自然数w。
 w×10000模7有7种可能，即是0，1，2，3，4，5，6，这时若能用数字1，2，3，4排列出7个数，
 使它们整除7取余的值分别为0，1，2，3，4，5，6。则把这个4位数接在w后面即为原问题的解。
 
 */
 /****************************************************************************/
 
 #include <stdlib.h>
 #include <stdio.h>
 #include <iostream.h>
 
 int main()
 {
 int data;
 scanf("%d",&data);//读取输入数据
 /**找出1,2,3,4组合中对7取余数分别为0,6,5,4,3,2,1,情况*/
 int add[7]={3241,2134,2413,1243,2341,1234,1324};
 int temp1=0;
 int temp2=0;
 bool flat[4]={false,false,false,false};//用于标记抽取到数字1,2,3,4的情况，即是验证输入数据是否符合要求
 /*以下循环把数字1,2,3，4从中抽取出来，然后其他数字按照原输入数据的逆序排成自然数*/
 while(data!=0)
 {
 temp1 = data%10;//抽取末位数字
 data = data/10;//去掉末位数字，向右移
 
 if((temp1==1 || temp1==2 || temp1==3 || temp1==4)&&(!flat[temp1-1]))
 {
 flat[temp1-1]=true;
 }
 else
 {
 			temp2 =temp2*10 + temp1;//如果不是数字1234则按照原输入数据的逆序排成自然数
 }
 }
 if(flat[0]&&flat[1]&&flat[2]&&flat[3])//判断输入数据是否合理
 {
 data=temp2*10000; //为后面的加运算腾出末四位数
 		temp2=data%7; //求余 
 if(temp2==0) //根据求出的余数加上由1,2，3,4组成的四位数
 		{
 			data = data+3241;
 		}
 		else if(temp2 ==6)
 		{
 			data = data+2134;
 		}
 		else if(temp2 ==5)
 		{
 			data = data+2413;
 		}
 		else if(temp2 ==4)
 		{
 			data = data+1243;
 		}
 		else if(temp2 ==3)
 		{
 			data = data+2341;
 		}
 		else if(temp2 ==2)
 		{
 			data = data+1234;
 		}
 		else if(temp2 ==1)
 		{
 			data = data+1324;
 		}
 printf("%d\n",data);//输出符合要求的结果
 }
 else
 {
 printf("the input is illegal\n");
 }
 	
 	return 0;
 }
 
 
 
 
 /******************** 心得体会 **********************/
 /*
 分析数据的关键部分在拆分数字部分
 */

运行结果：

![SouthEast 1][]

【未完待续】。。。。

[SouthEast]: /images/20220513/edb4adac131347019e4958574da7500a.png
[SouthEast 1]: /images/20220513/f913dd98c5234577aff08227e6ce7d9e.png