2020.1.29

数论（二）

1.引入

一开头讲了整除，质数，合数，质因数分解，带余除法，两数同余等小学基础知识，不加赘述。

有关推论：

1.约数总是成对出现

若 k 是 n 的约数, 则 (n/k) 也是 n 的约数。在一对约数中，必有一个不大于 √ n，另一个不小于 √ n。因此枚举 1..√ n 就能求出 n 的所有约数。

2.整除的表示

a|b表示：b%a=0

3.同余的表示

a ≡ b(mod c) 与 c|(a − b) 等价，表示：a%c=b%c

2.最大公约数

gcd(a,b)=gcd(a,a+b)=gcd(a,ka+b)

gcd(ka,kb) = k·gcd(a,b)

gcd(a,b,c)=gcd(gcd(a,b),c)

3.欧几里得算法(辗转相除法)

a>=b的前提下

由gcd(a,b)=gcd(a,ka+b)推得：gcd(a,b)=gcd(b,a%b)（k为a/b(整除)的相反数)

所以每次较大数都减少至少一半(取模运算，易证)

所以时间复杂度为O(log₂n)

4.裴蜀定理

若d=gcd(a,b),则对任意整数x,y有d|(ax + by)成立(理所当然地成立)

且一定有x,y满足ax+by=d（18和24：gcd(18,24)=6,(-1)·18+(1)·24=6）

5.扩展欧几里得算法

给上面的裴蜀定理推论的方程 ax+by=d 求解

考虑使用欧几里德算法的思想

d=gcd(a,b),令a=bq+r，r=a%b

由欧几里得算法可知gcd(a,b)=gcd(b,r)，方程化为bx₀+ry₀=d

最终，将化为gcd(d,0)=gcd(a,b)=d，方程化为dx_n+0y_n=d

显然，x_n=1,y_n=任意数

考虑如何把x_n,y_n变形成 ax + by = d 的解。

将a=bq+r代入ax+by=d得 –> (bq+r)x+by=d –> bqx+rx+by=d –> b(xq+y)+rx=d

因为bx₀+ry₀=d，故：x₀=xq+y，y₀=x

整理求出解：x=y₀，y=x₀-y₀q

边界条件 b=0时,x=1,y=0(本段第5行有交待)

代码实现

void kzojld(int a,int b,int $x,int $y) {//由于以后x，y要参与回溯，所以要传址调用
    if(!(b)) {//边界：b=0时，x=1，y=0()
        x=1;
        y=0;
        return;
    }
    int r=a%b;//记录模数
    int q=a/b;//记录倍数
    kzojld(b,r,y,x);//b,r的y变成a,b的x（x=y0）；b,r的x暂时作为a，b的y（y=x0-y0q,接下来还会进行处理）
    y-=x*q;//此时y=x0，在这样的基础上减去q*y0（x=y0）
    return;
}//不错，算是默写了（当然是看着上面的算法写的）

但是，怎样求出所有解呢？

先用扩展求出任意一个解 x₀,y₀

再求出ax+by=0的最小的解（x,y绝对值最小）

仍然是d=gcd(a,b)

这时设：d_x=x= b/d，d_y=y=−a/d （其实乘a或b以后，积的绝对值都是a,b的最小公倍数，必须一正一负，这样才能相加等于0）

原方程所有解就是,k取任意整数时的

x = x₀ + kd_x

y = y₀+ kd_y

所以x，y有无数组，利用这种方法可以求出第n小的解（绝对值）

洛谷网校：数论（一）