【算法】初等数论一些总结

科技前沿 • 2025-03-11 13:38 • 阅读 34

大家好，我是讯享网，很高兴认识大家。

然而实际上现在只有扩展欧里几德，也许之后会以此为据点(?)再写一些吧
~~就当又是来水博客的吧~~

扩展欧里几德

其实是将刘汝佳的紫书和林厚从的《数学一本通》稍稍总结了一下。
毕竟一个是“数学归纳法""此处略去”, 一个是代码硬是写了十几行

首先是林厚从的《信息学奥赛之数学一本通》(p10)中的逐步推出
为统一，将其原文中的p, q替换为x, y

… 因为 $\% b)$ ,
所以有 $由最大公约数性质，存在整数 x 、 y 满足 ① 式 a x + b y$ $= g c d (a, b)$ $\% b)$ $\% b)y$ $= b x + (a - a / b * b) y$ $上式拆开括号重新整理可得 ② 式 = a y + (x - a / b * y) b$

然后是刘汝佳的紫书(p313)（《算法竞赛入门经典》）中的精妙代码

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

讯享网

下面是作为参考的欧里几得法求最大公约数递归代码

讯享网int gcd(int a,int b) { 
    return !b ? a : gcd(b, a % b); }

读者可参考这篇博客，促进理解—— 这篇博客

讯享网

由最终推导式可看出①式中a的参数x变成了②式的y, ①式中b的参数y变成了②式的(x - a / b * y)
它们同样是由于最大公约数性质所以存在的两个数，这样的变化相当于随着欧里几得算法的递归，扩展欧里几得也在递归去找到这两个数
x, y的改变是代码中互换的原因, 但由于y实际不是成了x而是(x - a / b * y)
所以在x, y递归互换后(此时的x是上一步的y, y同理)将y -= x * (a / b)

~~所以说啊，作者们沟通一下多吼！~~

关于求其最小非负整数解

当然都知道怎么操作，但自己发现了原理中与缩系的一些联系
在转的这篇博客(也可以直接访问原博客)中受到的一些启发

关于这个内容，在所转博客中说得还可以，还加了小优化。但我也意外想到其与缩系的联系，就可以更加简单明了地解释了
扩展欧里几德求出来的只是一组特解，不能一定满足是最小非负整数解的情况
那我们就最好找到一个包含且仅包含最小非负整数解的范围，这样由于解是余数意义下的，我们就可以通过取模得到啦
先看条件为 $g c d (a, b) = 1$ , 所求是 $a x \equiv c (m o d b)$ 中的x时的情况
缩系有性质

b的缩系中的每个元素乘以一个与b互质的数在mod b意义下仍为b的缩系，每个元素在操作前唯一对应操作后的一个元素

将a看作缩系中乘上的数，那么x就一定可以是b的缩系中的值，换言之可以使$x \in [0, b) $，这样就一定是最小非负正整数解了，根据缩系性质此范围中也一定只有唯一解

那么 $g c d (a, b) = g$ 的时候呢？同样的，我们希望b在经过一些操作后能有 $g c d (a, b) = 1$ 。可以想到其实b/g后就能满足条件(可用反证法，若a, b仍不互质，那么仍有的不为1的约数应在之前被乘入g中，矛盾)
那么 $\in [0, b / g - 1)$

【算法】 初等数论 一些总结

扩展欧里几德

关于求其最小非负整数解

相关推荐

【算法】初等数论一些总结