SDAU暑假训练第一天----------数论（1）（2018/7/30）

本文主要是介绍SDAU暑假训练第一天----------数论（1）（2018/7/30），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

今天暑假训练就正式开始了，这个周是学习数论的相关知识。今天主要看了数论中整除的相关内容

话不多说，进入正题

整除

（一）基本概念：

（二）性质：

（三）特殊数字的整除性质：

补充整除知识：用“截尾法”判断整除性。

GCD与LCM

GCD

欧几里得

更相减损术

辗转相除法与更相减损术的比较

GCD的二进制写法（stein算法）

LCM

扩展欧几里得

贝祖等式

扩展欧几里得的代码

整除

（一）基本概念：

对于式子：ab=c…d

a被除数，b除数，c商，d余数

如果d=0，则称b整除a（或者a被b整除），记作b|a。如果d≠0，则b不能整除a记作b∤a。

（二）性质：

如果且，则
如果且 等价于对于任何整数，有
设m≠0，那么
如果a与b都能被c整除，则a+b与a-b也能被c整除；
如果a能被b整除，c是任意整数，则积ac也能被b整除；
如果a能同时被b、c整除，且b与c互质，那么a一定能被积bc整除，反之也成立；
任意整数都能被1整除，即1是任意整数的约数；0能被任意非0整数整除，即0是任意非0整数的倍数。

//这里尝试使用了公式编辑器进行公式编辑，然而CSDN不太支持并且用时间较多，所以后面放弃使用，以后学学markdown

（三）特殊数字的整除性质：

1、 2的幂次：如果2能整除n的最后一位，则2|n，若4能整除n的最后两位，则4|n，由此2^a如果能整除n的后a位，则（2^a）|n。

2、 3、9：如果3能整除n的各位数字之和，则3|n。如果9能整除n的各位数字之和，则9|n。

3、 11：若11能整除n的偶数位和奇数位数字之差，则11|n

4 、 7、11、13：n的后三位和后三位之前的数字所构成的数字之差能被7、11、13整除，则n被7 11 13 整除

5、一个整数的个位数字是2的倍数（0、2、4、6或8）或5的倍数（0、5），则这个数能被2或5整除；/6、若一个整数的十位和个位数字组成的两位数是4或25的倍数，则这个数能被4或25整除；

7、若一个整数的百位、十位和个位数字组成的三位数是8或125的倍数，则这个数能被8或125整除。

8、若一个数的末四位数能被16或625整除，则这个数能被16或625整除，依此类推。

/*例如判断710316的整除性

7 1 0 3 1 6 奇数位-偶数位=1+3+6-（7+0+1）=10-8=2 2∤11，所以不能被11整除

数位之和 7+1+0+3+1+6=18 9|18 所以被9整除*/

补充整除知识：用“截尾法”判断整除性。

　　①截尾减2法：若一个整数截去个位数字后，再从所得的数中，减去个位数字的2倍，差是7的倍数，则原数能被7整除；

　　②截尾减1法：若一个整数截去个位数字后，再从所得的数中，减去个位数字的1倍，差是11的倍数，则原数能被11整除；

　　③截尾加4法：若一个整数截去个位数字后，再从所得的数中，加上个位数字的4倍，差是13的倍数，则原数能被13整除；

　　④截尾减5法：若一个整数截去个位数字后，再从所得的数中，减去个位数字的5倍，差是17的倍数，则原数能被17整除；

　　⑤截尾加2法：若一个整数截去个位数字后，再从所得的数中，加上个位数字的2倍，差是19的倍数，则原数能被19整除。

　　根据整除的基本性质（3），以上5条整除特征中，如果差太大，可以继续前面的“截尾翻倍相加”或“截尾翻倍相减”的过程，直到能直接判断为止。

　　【推理过程】：

　　设任意一个整数的个位数字为y，这个数可以表示成10x＋y的形式，其中x为任意整数。

　　一个数截尾减2后，所得数为（x－2y）。因为截去这个数的个位数字后，所得数x减去个位数字y的2倍，实际上是在原数的十位数字上减去2个y，即减去了20个y，截尾一个y，总共减去了21个y，剩下了（x－2y）个10。如下式：10x－20y＋y－y﹦（x－2y）×10﹦（10x＋y）－21y。

　　根据整除的基本性质，如果（x－2y）能被7整除，则（x－2y）×10就能被7整除，即（10x＋y）－21y能被7整除，21y是7的倍数，可以推出原数（10x＋y）一定能被7整除。

　　“截尾加4”就是原数截去1个y、加上40个y，总共加了39y（13的倍数），得到（x＋4y）个10，“截尾加4”所得（x＋4y）如果能被13整除，原数必能被13整除。

　　同理，“截尾减1”就是原数减去了11个y（11的倍数），原数剩下（x－y）个10，“截尾减1”所得（x－y）能被11整除，原数必能被11整除；

　　“截尾减5”就是原数减去了51个y（17的倍数），原数剩下（x－5y）个10，“截尾减5”所得（x－5y）能被17整除，原数必能被17整除；

　　“截尾加2”就是原数加了19y（19的倍数），得到（x＋2y）个10，“截尾加2” 所得（x＋2y）如果能被19整除，原数必能被19整除。

　　依此类推，可以用“截尾加3”判断一个数能否被29整除，用“截尾减4”判断一个数能否被41整除等等。

　　（4） “截尾法”的推广使用。

　　①若一个数的末三位数与末三位之前的数字组成的数相减之差（大数减小数）能被7、11或13整除，则这个数一定能被7、11或13整除；

　　②若一个整数的末四位与之前数字组成数的5倍相减之差能被23或29整除，则这个数能被23或29整除。（比较适合对五位数进行判断）

　　【推理过程】：

　　①设任意一个整数的末三位数为y，则这个数可以表示成1000x＋y的形式，其中x为任意整数。

　　当x大于y时，这个数末三位之前的数字组成的数减去末三位数得到（x－y）。这里x减y实际上是在原数的千位上减去y，即减去了1000y，加上截去末三位数y，总共减去了1001y，原数剩下（x－y）个1000。如下式：

　　1000x－1000y＋y－y﹦1000（x－y）﹦（1000x＋y）－1001y

　　7×11×13﹦1001，7、11和13都是1001的因数。

　　综上所述，如果这个数末三位之前的数字组成的数减去末三位数得到（x－y）能被7、11或13整除，即（1000x＋y）－1001y能被7、11或13整除，则原数必能被7、11或13整除。

　　当y大于x时，可得1000（y－x）﹦1001y－（1000x＋y），如果（y－x）能被7、11或13整除，则原数必能被7、11或13整除。

　　②设任意一个整数的末四位数为y，则这个数可以表示成10000x＋y的形式，其中x为任意整数。末四位与之前数字组成数的5倍相减之差即（y－5x）。

　　10000（y－5x）﹦1005y－5（10000x＋y）

　　因为1005是23和29的公倍数，如果一个数末四位与之前数字组成数的5倍相减之差即（y－5x）能被23或29整除，即10000（y－5x）能被23或29整除，则原数必能被23或29整除。

　　依此类推，如果一个数末两位数与之前数字相减之差能被101整除，则这个数必能被101整除等等。

GCD与LCM

GCD

欧几里得

递归写法


形式1：
int gcd(int a,int b)
{if(b==0) return a;return gcd(b,a%b);
}
形式2：
int gcd(int x,int y){return y==0?x:GCD(x%y)}

非递归写法

int gcd(int a,int b)
{while(b){a=a%b;swap(a,b);}return a;
}

更相减损术

while(!(a%2) && !(b%2))
{a = a/2;b = b/2;
}
while(a != b)
{if(a>b){a = a-b;}else{b = b-a;}
}

辗转相除法与更相减损术的比较

（1）两者都是求最大公因数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。

（2）更相减损术本质是辗转相除法，辗转相除法效率比较高

（3）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

GCD的二进制写法（stein算法）

二进制写法先用移位的方式对两个数除2，直到两个数不同时为偶数。然后将剩下的偶数（如果有的话）做同样的操作，这样做的原因是如果u和v中u为偶数,v为奇数，则有gcd(u,v)=gcd(u/2,v)。到这时，两个数都是奇数，将两个数相减(因为gcd(u,v) = gcd(u-v,v))，得到的是偶数t，对t也移位直到t为奇数。每次将最大的数用t替换。

Stein算法只有整数的移位和加减法。下面就来说一下Stein算法的原理：

不加证明的给出：

若a和b都是偶数，则记录下公约数2，然后都除2（即右移1位）；
若其中一个数是偶数，则偶数除2，因为此时2不可能是这两个数的公约数了
若两个都是奇数，则a = |a-b|，b = min(a,b)，因为若d是a和b的公约数，那么d也是|a-b|和min(a,b)的公约数。

递归式：

int SteinGCD(int a, int b) {if (a < b) { int t = a; a = b; b = t; }if (b == 0) return a;if ((a & 1) == 0 && (b & 1) == 0)return SteinGCD(a >> 1, b >> 1) << 1;else if ((a & 1) == 0 && (b & 1) != 0)return SteinGCD(a >> 1, b);else if ((a & 1) != 0 && (b & 1) == 0)return SteinGCD(a, b >> 1);elsereturn SteinGCD(a - b, b);
}

非递归：

int SteinGCD(int a, int b) {int acc = 0;while ((a & 1) == 0 && (b & 1) == 0) {acc++;a >>= 1;b >>= 1;}while ((a & 1) == 0) a >>= 1;while ((b & 1) == 0) b >>= 1;if (a < b) { int t = a; a = b; b = t; }while ((a = (a - b) >> 1) != 0) {while ((a & 1) == 0) a >>= 1;if (a < b) { int t = a; a = b; b = t; }}return b << acc;
}

LCM

LCM(A,B)=A*B/GCD(A,B)；

扩展欧几里得

扩展欧几里得算法，就和它的名字一样是对欧几里得算法的扩展。何为扩展？一是，该算法保留了欧几里得算法的本质，可以求a与b的最大公约数。二是，已知a, b求解二元一次方程ax+by =gcd(a, b)的一组解（x，y）。

贝祖等式

对于任何整数a、b和他们的最大公约数gcd(a, b)，一定有未知整数x和y满足一下等式： ax+by=gcd(a,b)
例如：12和42的最大公约数为6，则方程12x+42y=612x+42y=6。事实上有(−3)×12+1×42=6(−3)×12+1×42=6及4×12+(−1)×42=64×12+(−1)×42=6。

扩展欧几里得的代码

友情链接：https://blog.csdn.net/sdutstudent/article/details/78795643

void e_gcd(int a, int b, int &gcd, int &x, int &y)
{if (b == 0){x = 1;y = 0;gcd = a;}else{e_gcd(b, a % b, gcd, y, x);y -= x * (a / b)}
}

递归

int ExtendGCD(int a, int b, int *x, int *y) {if (b == 0) {*x = 1; *y = 0; // b=0return a;}int r = ExtendGCD(b, a%b, x, y);int t = *y; // temp*y = *x - (a / b)*(*y); // y1 = x2 - k*y2*x = t; // x1 = y2return r;
}

极度简化版：

void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y){
2     if(!b){d = a; x = 1; y = 0;}
3     else{ex_gcd(b, a%b, d, y, x); y -= x*(a/b);}
4 }

非递归

int ExtendGCD(int a, int b, int *x, int *y)
{if (b == 0) { *x = 1; *y = 0; return a; }int r = a % b;int x0 = 1, x1 = 0; // x1 = y0 = 0int y0 = 0, y1 = 1; // y1 = x0 - k*y0 = 1while (r != 0){*x = x0 - a / b * y0;*y = x1 - a / b * y1; x0 = y0;x1 = y1;y0 = *x;y1 = *y;a = b; b = r; r = a % b;}return b;
}

我数学基础比起别的大佬们差一些，进度不算是很快，但是多投入一些时间就好了。

明天继续加油

这篇关于SDAU暑假训练第一天----------数论（1）（2018/7/30）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！