2025.2.7

· · 个人记录

集训第二天，寒假快结束了，作业却没有一丝岁月的痕迹qaq

数学知识

今天学习了最大公约数与欧拉函数的知识，我们小组负责的是最大公约数。(导致欧拉函数基本没懂)

所以本文主要总结一些最大公约数的定义，定理与求法。

1.定义

现有两个自然数 a 与 b ，还有一个集合 Cm。

而其中最大的就是**最大公约数**，记为$gcd(a,b)$。 不要小看这简单的定义，接下来要证的东西不仅与它们关联还十分讲究严谨性。(~~了解我的人都知道，我的数学不太好qaq~~) ## 2.定理 $\forall x,y \in \mathbb{N},gcd(x,y) \times lcm(x,y) = x \times y

证明：

设 d = gcd(x,y),a = x{\div}d,b = y{\div}d。

因为 d 是 x 与 y 最大的约数，所以 a 与 b 互质。gcd(a,b) 一定为 1。

又因为 a 与 b 互质，所以 lcm(a,b) = a \times b 。

于是 lcm(x,y) = lcm(a \times d,b \times d) = lcm(a,b) \times d = a \times b \times d = (x {\div} d) \times (y {\div} d) \times d = x \times y {\div} d 。

大功告成！！！

3.求法

想求最大公约数，有两种常用的方法，更相减损术与欧几里得算法(辗转相除法)。

更相减损术

\mathrm{可半者半之，不可半者，副置分母、子之数，} \mathrm{以少减多，更相减损，求其等也。以等数约之。}

这是在《九章算术》中更相减损术的记载。

这种方法原本是为约分而设计的，但它适用于任何需要求最大公约数的场合。

用法

第一步：任意给定两个正整数；判断它们是否都是偶数。若是，则用2约简；若不是则执行第二步。

第二步：以较大的数减较小的数，接着把所得的差与较小的数比较，并以大数减小数。继续这个操作，直到所得的减数和差相等为止。

则第一步中约掉的若干个2的积与第二步中等数的乘积就是所求的最大公约数。

其中所说的“等数”，就是公约数。求“等数”的办法是“更相减损”法。

证明

\forall x,y \in \mathbb{N},$ 有 $gcd(b,a-b) = gcd(a,a-b)

证明：

设 d=gcd(x,y),a=x{\div}d,b=y{\div}d

c=x+y=a \times d+b \times d = (a-b) \times d

因为 a 与 b 均为正整数，所以 c 也能被 d 整除，即 x,y,c 的最大公约数均为 d

大功告成！！！

代码实现

int gcd_More derogation(int a,int b){
    int t = abs(a-b);
    while(t != 0){
        a = b;
        b = t;
        t = abs(a-b);
    }
    return b;
}