需要知识
同余
数论中的重要概念。给定一个正整数m,如果两个整数a和b满足(a-b)能够整除m,即(a-b)/m得到一个整数,那么就称整数a与b对模m同余,记作a≡b(mod m)。对模m同余是整数的一个等价关系。——百度百科
关于同余的定理
欧几里德算法
辗转相除法, 又名欧几里德算法(Euclidean algorithm)乃求两个正整数之最大公因子的算法。它是已知最古老的算法, 其可追溯至3000年前。
这种算法,在中国则可以追溯至东汉出现的《九章算术》。——百度百科
简单明了的最大公因数计算算法。
int gcd(int a,int b){ return b==0?a:gcd(b,a%b); }
证明如下
- 有整数X,Y。其中,X=ar,Y=br(a,b互质,且r为最大公因数)。有X-Y=(a-b)*r。则,X、Y、X-Y互相间最大公因数相同。
- 有整数X,Y。其中,X=ar+c,Y=br+d(r为最大公因数,且c,d小于r)。设e=X%Y,也即(e+d+br)n=ar+c,有e=ar+c-d-b*r=(a-b)*r+(c-d),所以X、Y、X%Y互相间最大公因数相同。