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

数学知识

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

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

1.定义

现有两个自然数

a

与

b

，还有一个集合

Cm

。

Cm

里的数都同时是

a

与

b

的约数，它们就是

a

与

b

的公约数。

而其中最大的就是最大公约数，记为

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

大功告成！！！

代码实现

CPP

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;
}

2025.2.7

文章操作