初级数论之：两个数的最大公约数的递推公式【更相减损术】【辗转相除法】

1. 公式
   观察依据

   文档中反复出现 $\gcd(a,b)$，代码中调用 $\gcd(a,b)$。

2. 声音
   观察依据

   讲解者多次说“最大公约数”。

$\gcd$

两个整数的最大公约数函数。

视频未说明具体定义域；示例中使用非负整数。

1. 公式
   观察依据

   文档公式写为 $\gcd(a,b)=\gcd(b,a-k\cdot b)$。

2. 公式
   观察依据

   代码中声明 `const int $a = 24$;` 与 `const int $b = 504$;`。

$a,b$

参与求最大公约数的两个整数。

示例中为整数；视频未给出一般限制。

1. 公式
   观察依据

   文档写“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”。

2. 声音
   观察依据

   讲解者说“首先设 $k$ 为任意的整数”。

3. 公式
   观察依据

   代码循环写为 `for (int $k=-1024$;k<=1024;++k)`。

$k$

递推公式中可任取的整数参数。

任意整数。

1. 公式
   观察依据

   文档写 $\gcd(a,b)=\gcd(b,a\bmod b)$。

1. 视频未解释 `mod` 的取余定义、符号约定或 $b=0$ 时的处理。

$a\bmod b$

辗转相除法公式中的取余项。

视频未说明。

1. 公式
   观察依据

   文档写“令 $k=\lfloor a/b\rfloor$”。

1. 视频未说明 $b=0$ 时该表达式无定义。

$\lfloor a/b\rfloor$

对 $a/b$ 取向下取整得到的整数商。

视频未说明。

1. 公式
   观察依据

   代码中出现 `const int $a = 24$;`、`const int $b = 504$;`、`for (int $k=-1024$;k<=1024;++k)`。

`int`

C++ 中用于声明示例变量的整数类型。

视频未说明取值范围。

1. 公式
   观察依据

   代码中写 `cout << gcd(a, b) << endl;`。

2. 声音
   观察依据

   讲解者说“我这里直接用了 gcd 这个函数……我的 C++ 的版本现在比较新，所以它自带了 gcd 这个函数”。

1. 视频未说明所用标准库头文件；画面可见 `#include <bits/stdc++.h>`。

`gcd(a, b)`

C++ 代码中对最大公约数函数的调用。

示例中传入两个 `int`。

1. 公式
   观察依据

   代码第6行 `const int $a = 24$;`；讲义第1节公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$ 中出现 $a$

2. 声音
   观察依据

   讲解者在推导 $k=\lfloor a/b\rfloor$ 时说“$a$ 除以 $b$ 的商”

a

参与最大公约数计算的第一整数；在代码示例中取值为 24

整数

1. 公式
   观察依据

   代码第7行 `const int $b = 504$;`；讲义第1节公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$ 中出现 $b$

2. 声音
   观察依据

   讲解者说“$a$ 除以 $b$ 下下去整”

b

参与最大公约数计算的第二整数；在代码示例中取值为 504

整数

1. 公式
   观察依据

   代码第8行 `const int c = gcd(a, b);`；第11行 `if (c != gcd(b, $a - k * b$))`

2. 声音
   观察依据

   讲解者说“如果 c 不等于它”

c

代码中保存 $\gcd(a,b)$ 结果的变量

整数

1. 公式
   观察依据

   代码第10行 `for (int $k=-1024$; k<=1024; ++k)`；讲义第1节“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”

2. 声音
   观察依据

   讲解者说“对于任意的 $k$”“比如说 $k$ 等于 1 的时候”“令 $k$ 等于 $a$ 除以 $b$ 下下去整”

k

递推公式中的整数参数；代码中遍历范围为 -1024 到 1024

整数

1. 公式
   观察依据

   代码第8行 `gcd(a, b)`；讲义第1节公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$

2. 声音
   观察依据

   讲解者读出“gcd a b 等于 gcd b a 减 k 倍的 b”

$\gcd$

最大公约数函数

作用于两个整数，返回整数

1. 公式
   观察依据

   文档标题为“两个数的最大公约数的递推公式”。

2. 公式
   观察依据

   文档正文写“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”。

3. 声音
   观察依据

   讲解者说“这一次呢我们来讲一下求两个数的最大公约数的递推公式”“首先设 $k$ 为任意的整数，则 $a$ 和 $b$ 的最大公约数等于 $b, a$ 减去 $k$ 倍的 $b$ 的最大公约数”。

视频给出的核心公式把 $\gcd(a,b)$ 转化为 $\gcd(b,a-k\cdot b)$，其中 $k$ 可任取整数。讲解者强调对新学竞赛而言掌握这一个公式即可。

1. $k$ 为任意整数。

2. 视频未说明 $a,b$ 的额外限制。

1. 公式
   观察依据

   文档小节标题为“1.1 更相减损术”。

2. 公式
   观察依据

   文档写“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”。

这是核心递推公式在 $k=1$ 时的特例，每次把第一参数替换为两数之差。

1. 由核心公式令 $k=1$ 得到。

2. 视频未说明 $a,b$ 的大小关系或正负限制。

1. 两个数最大公约数的递推公式

1. 公式
   观察依据

   文档小节标题为“1.2 辗转相除法”。

2. 公式
   观察依据

   文档写“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”。

1. 视频未解释 `mod` 的定义、$b=0$ 的处理或向下取整商与余数的关系。

这是核心递推公式在 $k=\lfloor a/b\rfloor$ 时的特例，把第一参数替换为 $a$ 除以 $b$ 的余数。

1. 由核心公式令 $k=\lfloor a/b\rfloor$ 得到。

2. 视频未说明 $b\neq 0$ 这一通常所需前提。

1. 两个数最大公约数的递推公式

1. 公式
   观察依据

   代码中调用 `gcd(a, b)`。

2. 声音
   观察依据

   讲解者说“我这里直接用了 gcd 这个函数，那是因为我的 C++ 的版本啊现在比较新啊，所以它自带了 gcd 这个函数”。

3. 声音
   观察依据

   讲解者又说“但是你考试的时候那个 C++ 编译器的版本不一定有这么新啊，所以你考试的时候那个 gcd 这个函数也要自己实现的啊，我们等会儿再讲怎么实现的啊”。

1. 视频未说明具体 C++ 标准版本或头文件；画面可见 `#include <bits/stdc++.h>`。

视频用较新的 C++ 环境演示直接调用 `gcd(a,b)` 计算最大公约数，同时提醒考试环境未必支持该内置函数，需要自行实现。

1. 视频称当前 C++ 版本较新。

2. 视频未说明具体标准版本。

1. 公式
   观察依据

   讲义标题“1 两个数的最大公约数的递推公式”；正文“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”

2. 声音
   观察依据

   讲解者说“对于任意的 $k$，gcd a b 等于 gcd b a 减 $k$ 倍的 $b$，总是成立的”“我们要掌握的第一个系统化的专业的递推公式”

视频给出最大公约数的递推恒等式：对任意整数 $k$，$\gcd(a,b)=\gcd(b,a-k\cdot b)$。该公式把 $(a,b)$ 的最大公约数转化为 $(b,a-kb)$ 的最大公约数，是后续更相减损术和辗转相除法的统一来源。

1. $a,b$ 为整数

2. $k$ 为任意整数

1. 公式
   观察依据

   讲义第1.1节“更相减损术”；“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”

2. 声音
   观察依据

   讲解者说“比如说 $k$ 等于 1 的时候，我们就得到 gcd a b 等于 gcd b a 减 b，这就是大名鼎鼎的更相减损术”

在递推公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$ 中取 $k=1$，得到 $\gcd(a,b)=\gcd(b,a-b)$。视频将此特例命名为更相减损术。

1. $k=1$

2. $a,b$ 为整数

1. 两个数的最大公约数的递推公式

1. 公式
   观察依据

   讲义第1.2节“辗转相除法”；“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”

2. 声音
   观察依据

   讲解者说“如果令 $k$ 等于 $a$ 除以 $b$ 下下去整……我们就得到 gcd a b 等于 gcd b a 模 b 的余数，这个就是大名鼎鼎的辗转相除法”

在递推公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$ 中取 $k=\lfloor a/b\rfloor$，则 $a-kb=a-(\lfloor a/b\rfloor)b$ 是 $a$ 除以 $b$ 的余数，因此得到 $\gcd(a,b)=\gcd(b,a\bmod b)$。视频将此特例命名为辗转相除法。

1. $k=\lfloor a/b\rfloor$

2. $a,b$ 为整数

3. 视频未说明 $b\neq 0$

1. 两个数的最大公约数的递推公式

1. 公式
   观察依据

   文档写“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”。

2. 声音
   观察依据

   讲解者复述该公式并称“就是这个公式啊”。

1. 视频未给出证明。

对于任意整数 $k$，有 $\gcd(a,b)=\gcd(b,a-k\cdot b)$。

1. $k$ 为任意整数。

2. 视频未说明 $a,b$ 的额外限制。

对任意整数 $k$ 成立。

1. 公式
   观察依据

   文档写“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”。

令 $k=1$ 时，核心递推公式化为 $\gcd(a,b)=\gcd(b,a-b)$。

1. 核心公式成立。

2. 取 $k=1$。

在视频给出的公式框架下直接代入。

1. 公式
   观察依据

   文档写“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”。

1. 视频未说明 $b\neq 0$ 以及 `mod` 的精确定义。

令 $k=\lfloor a/b\rfloor$ 时，核心递推公式化为 $\gcd(a,b)=\gcd(b,a\bmod b)$。

1. 核心公式成立。

2. 取 $k=\lfloor a/b\rfloor$。

3. 视频未说明但通常需 $b\neq 0$。

在视频给出的公式框架下直接代入。

1. 公式
   观察依据

   代码中 `const int $a = 24$;`、`const int $b = 504$;`。

2. 公式
   观察依据

   终端输出 `24`。

3. 声音
   观察依据

   讲解者说“算出来等于 24 啊”“当 $a=24, b=504$ 的时候，它们的最大公约数的答案是 24”。

在该示例中，$\gcd(24,504)=24$。

1. $a=24$。

2. $b=504$。

针对给定数值实例。

1. 声音
   观察依据

   讲解者说“但是你考试的时候那个 C++ 编译器的版本不一定有这么新啊，所以你考试的时候那个 gcd 这个函数也要自己实现的啊”。

1. 视频未说明具体考试平台或编译器版本。

视频提醒考试时 C++ 编译器版本可能较旧，不能假定 `gcd` 函数一定可用，需要自行实现。

1. 考试环境的 C++ 编译器版本可能不如演示环境新。

视频以一般性提醒表述，未给出形式化量词。

1. 声音
   观察依据

   讲解者说“也就是说对于任意的 $k$，gcd a b 等于 gcd b a 减 $k$ 倍的 $b$，总是成立的”

2. 公式
   观察依据

   讲义第1节写出“对于任意整数 $k$ 都有：$\gcd(a,b)=\gcd(b,a-k\cdot b)$”

3. 图示
   观察依据

   终端运行程序后只输出 `**********`，没有输出任何使条件 `c != gcd(b, $a - k * b$)` 成立的 $k$

对于任意整数 $k$，都有 $\gcd(a,b)=\gcd(b,a-k\cdot b)$。

1. $a,b$ 为整数

2. $k$ 为任意整数

任意整数 $k$

1. 公式
   观察依据

   讲义第1.1节“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”

2. 声音
   观察依据

   讲解者说“$k$ 等于 1 的时候，我们就得到 gcd a b 等于 gcd b a 减 b，这就是大名鼎鼎的更相减损术”

令 $k=1$，递推公式 $\gcd(a,b)=\gcd(b,a-k\cdot b)$ 化为 $\gcd(a,b)=\gcd(b,a-b)$。

1. $a,b$ 为整数

2. $k=1$

存在特定取值 $k=1$

1. 公式
   观察依据

   讲义第1.2节“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”

2. 声音
   观察依据

   讲解者说“如果令 $k$ 等于 $a$ 除以 $b$ 下下去整……我们就得到 gcd a b 等于 gcd b a 模 b 的余数，这个就是大名鼎鼎的辗转相除法”

1. 视频未明确说明 $b\neq 0$ 这一除法前提

令 $k=\lfloor a/b\rfloor$，则 $a-kb=a\bmod b$，从而 $\gcd(a,b)=\gcd(b,a\bmod b)$。

1. $a,b$ 为整数

2. $k=\lfloor a/b\rfloor$

3. 视频未说明 $b\neq 0$

存在特定取值 $k=\lfloor a/b\rfloor$

1. 公式
   观察依据

   文档先给出 $\gcd(a,b)=\gcd(b,a-k\cdot b)$，随后写“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”。

1. 公式

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   解释

   从视频给出的核心递推公式出发。

   步骤依据

   文档直接给出该公式。

   视频直接表达
2. 公式

   $$k=1$$
   解释

   将参数 $k$ 取为 1。

   步骤依据

   文档写“令 $k=1$”。

   视频直接表达
3. 公式

   $$\gcd(a,b)=\gcd(b,a-b)$$
   解释

   代入后得到更相减损术形式。

   步骤依据

   把 $k=1$ 代入 $a-k\cdot b=a-b$。

   依据视频推导

更相减损术 $\gcd(a,b)=\gcd(b,a-b)$ 是核心递推公式在 $k=1$ 时的特例。

1. 公式
   观察依据

   文档先给出 $\gcd(a,b)=\gcd(b,a-k\cdot b)$，随后写“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”。

1. 视频未展示从 $a-\lfloor a/b\rfloor b$ 到 $a\bmod b$ 的中间说明。

1. 公式

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   解释

   从视频给出的核心递推公式出发。

   步骤依据

   文档直接给出该公式。

   视频直接表达
2. 公式

   $$k=\lfloor a/b\rfloor$$
   解释

   将参数 $k$ 取为 $a/b$ 的向下取整。

   步骤依据

   文档写“令 $k=\lfloor a/b\rfloor$”。

   视频直接表达
3. 公式

   $$\gcd(a,b)=\gcd(b,a\bmod b)$$
   解释

   代入后得到辗转相除法形式。

   步骤依据

   文档直接给出该结论；补充解释：通常因为 $a\bmod b=a-\lfloor a/b\rfloor b$。

   视频直接表达

辗转相除法 $\gcd(a,b)=\gcd(b,a\bmod b)$ 是核心递推公式在 $k=\lfloor a/b\rfloor$ 时的特例。

1. 公式
   观察依据

   代码设置 `const int $a = 24$;`、`const int $b = 504$;`。

2. 公式
   观察依据

   终端输出 `24`。

3. 声音
   观察依据

   讲解者说“算出来等于 24 啊”。

1. 公式

   $$a=24,\quad b=504$$
   解释

   设定示例数值。

   步骤依据

   代码中声明这两个常量。

   视频直接表达
2. 公式

   $$\gcd(24,504)$$
   解释

   调用最大公约数函数计算示例值。

   步骤依据

   代码写 `cout << gcd(a, b) << endl;`。

   视频直接表达
3. 公式

   $$24$$
   解释

   程序输出结果为 24。

   步骤依据

   终端显示 `24`，讲解者也口头确认。

   视频直接表达

示例数值 $a=24, b=504$ 时，视频通过程序输出验证 $\gcd(24,504)=24$。

1. 公式
   观察依据

   代码第6-12行：`const int $a = 24$; const int $b = 504$; const int c = gcd(a, b); for (int $k=-1024$; k<=1024; ++k) { if (c != gcd(b, $a - k * b$)) { cout << k << endl; } }`

2. 图示
   观察依据

   终端第31-33秒显示编译运行后输出 `**********`，没有输出任何 $k$ 值

3. 声音
   观察依据

   讲解者说“你会发现啊，这个程序是不是只输出了一堆星号”“也就是说对于任意的 $k$，gcd a b 等于 gcd b a 减 $k$ 倍的 $b$，总是成立的”

1. 代码中 `#define int int64_t` 将 `int` 重定义为 64 位整数，但视频未解释其对示例数值范围的影响

1. 公式

   $$a=24,\ b=504,\ c=\gcd(a,b)$$
   解释

   代码先固定 $a=24$、$b=504$，并把 $\gcd(a,b)$ 存入变量 $c$。

   步骤依据

   视频代码第6-8行直接给出。

   视频直接表达
2. 公式

   $$\text{for }k=-1024,-1023,\ldots,1024:\ \text{check } c\neq \gcd(b,a-kb)$$
   解释

   程序遍历整数 $k$ 从 -1024 到 1024，检查 $\gcd(a,b)$ 是否不等于 $\gcd(b,a-kb)$。

   步骤依据

   视频代码第10-11行直接给出。

   视频直接表达
3. 公式

   $$\text{output only } **********$$
   解释

   运行结果没有出现任何满足 `c != gcd(b, $a - k * b$)` 的 $k$，只输出循环结束后的星号标记。

   步骤依据

   终端第31-33秒显示输出为 `**********`。

   视频直接表达
4. 公式

   $$\gcd(24,504)=\gcd(504,24-k\cdot 504)\ \text{for tested } k$$
   解释

   由测试范围内未找到反例，讲解者据此说明该递推等式对任意整数 $k$ 成立。

   步骤依据

   讲解者在第39-48秒总结“对于任意的 $k$……总是成立的”。

   视频直接表达

代码枚举验证支持 $\gcd(a,b)=\gcd(b,a-kb)$ 在测试范围内无反例，讲解者将其推广为任意整数 $k$ 下成立。

1. 公式
   观察依据

   讲义第1节 $\gcd(a,b)=\gcd(b,a-k\cdot b)$；第1.1节“令 $k=1$，就得到更相减损术：$\gcd(a,b)=\gcd(b,a-b)$”

2. 声音
   观察依据

   讲解者说“比如说 $k$ 等于 1 的时候，我们就得到 gcd a b 等于 gcd b a 减 b，这就是大名鼎鼎的更相减损术”

1. 公式

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   解释

   从视频给出的一般递推公式出发。

   步骤依据

   讲义第1节公式。

   视频直接表达
2. 公式

   $$k=1$$
   解释

   令参数 $k$ 取 1。

   步骤依据

   讲义第1.1节“令 $k=1$”。

   视频直接表达
3. 公式

   $$\gcd(a,b)=\gcd(b,a-b)$$
   解释

   代入后得到更相减损术形式。

   步骤依据

   将 $k=1$ 代入 $a-kb$ 得 $a-b$。

   依据视频推导

更相减损术 $\gcd(a,b)=\gcd(b,a-b)$ 是一般递推公式在 $k=1$ 时的特例。

1. 公式
   观察依据

   讲义第1节 $\gcd(a,b)=\gcd(b,a-k\cdot b)$；第1.2节“令 $k=\lfloor a/b\rfloor$，就得到辗转相除法：$\gcd(a,b)=\gcd(b,a\bmod b)$”

2. 声音
   观察依据

   讲解者说“$a$ 除以 $b$ 下下去整就是 $a$ 除以 $b$ 的商”“被除数减去商乘以除数就等于余数”

3. 动画
   观察依据

   第99-107秒在公式 $a-k\cdot b$ 上方手写标注 $a-\lfloor a/b\rfloor b$，随后指向 $a\bmod b$

1. 视频未明确说明 $b\neq 0$ 这一除法前提

1. 公式

   $$\gcd(a,b)=\gcd(b,a-k\cdot b)$$
   解释

   从视频给出的一般递推公式出发。

   步骤依据

   讲义第1节公式。

   视频直接表达
2. 公式

   $$k=\lfloor a/b\rfloor$$
   解释

   令参数 $k$ 取 $a$ 除以 $b$ 向下取整，即商。

   步骤依据

   讲义第1.2节“令 $k=\lfloor a/b\rfloor$”；讲解者称其为“$a$ 除以 $b$ 的商”。

   视频直接表达
3. 公式

   $$a-k\cdot b=a-\lfloor a/b\rfloor b$$
   解释

   把 $k=\lfloor a/b\rfloor$ 代入第二参数。

   步骤依据

   代数代入。

   依据视频推导
4. 公式

   $$a-\lfloor a/b\rfloor b=a\bmod b$$
   解释

   讲解者说明被除数减去商乘以除数等于余数。

   步骤依据

   讲解者第107-112秒口述“被除数减去商乘以除数就等于余数”。

   视频直接表达
5. 公式

   $$\gcd(a,b)=\gcd(b,a\bmod b)$$
   解释

   得到辗转相除法形式。

   步骤依据

   讲义第1.2节公式。

   视频直接表达

辗转相除法 $\gcd(a,b)=\gcd(b,a\bmod b)$ 是一般递推公式在 $k=\lfloor a/b\rfloor$ 时的特例。

1. 公式
   观察依据

   代码中 `const int $a = 24$;`、`const int $b = 504$;`、`cout << gcd(a, b) << endl;`。

2. 公式
   观察依据

   终端输出 `24`。

3. 声音
   观察依据

   讲解者说“比如说我们举一个例子”“令整数 $a$ 等于……24”“令整数 $b$ 等于……504”“算出来等于 24 啊”。

给定两个整数 $a=24$、$b=504$，求它们的最大公约数。

1. $a=24$。

2. $b=504$。

3. 使用 C++ 代码调用 `gcd(a,b)`。

计算 $\gcd(24,504)$ 并输出结果。

1. 公式

   $$const int a = 24;$$
   解释

   在代码中声明第一个整数。

   步骤依据

   画面可见代码行。

   视频直接表达
2. 公式

   $$const int b = 504;$$
   解释

   在代码中声明第二个整数。

   步骤依据

   画面可见代码行。

   视频直接表达
3. 公式

   $$cout << gcd(a, b) << endl;$$
   解释

   调用 `gcd` 函数并输出结果。

   步骤依据

   画面可见代码行；讲解者说明直接使用 C++ 自带的 `gcd` 函数。

   视频直接表达
4. 公式

   $$24$$
   解释

   终端显示程序输出。

   步骤依据

   画面终端区域显示 `24`。

   视频直接表达

$\gcd(24,504)=24$。

视频通过运行 C++ 程序并在终端输出 24 来验证结果。

1. 公式
   观察依据

   代码第6-15行完整可见：`const int $a = 24$; const int $b = 504$; const int c = gcd(a, b); for (int $k=-1024$; k<=1024; ++k) { if (c != gcd(b, $a - k * b$)) { cout << k << endl; } } cout << "**********" << endl;`

2. 图示
   观察依据

   终端第31-33秒显示 `$ $g++ a$.cpp && ./a.out` 后输出 `**********`

3. 声音
   观察依据

   讲解者说“你会发现啊，这个程序是不是只输出了一堆星号”

1. 视频未展示 `gcd` 函数的实现，只展示调用结果

给定 $a=24$、$b=504$，令 $c=\gcd(a,b)$，遍历整数 $k$ 从 -1024 到 1024，检查是否存在 $c\neq\gcd(b,a-kb)$。

1. $a=24$

2. $b=504$

3. $c=\gcd(a,b)$

4. $k\in[-1024,1024]$

判断测试范围内是否有 $k$ 使 $\gcd(a,b)\neq\gcd(b,a-kb)$。

1. 公式

   $$c=\gcd(24,504)$$
   解释

   先计算并保存 $\gcd(a,b)$。

   步骤依据

   代码第8行 `const int c = gcd(a, b);`。

   视频直接表达
2. 公式

   $$\text{for }k=-1024\text{ to }1024:\ \text{if }(c\neq\gcd(504,24-k\cdot 504))\ \text{print }k$$
   解释

   对每个整数 $k$ 检查等式是否失败，若失败则输出 $k$。

   步骤依据

   代码第10-12行。

   视频直接表达
3. 公式

   $$\text{print }**********$$
   解释

   循环结束后输出星号标记，表示程序运行完成。

   步骤依据

   代码第15行；讲解者说“为了标称我整个程序已经运行完了，我们最后输出一堆星号”。

   视频直接表达
4. 公式

   $$\text{terminal output: }**********$$
   解释

   实际终端只显示星号，没有显示任何 $k$。

   步骤依据

   终端第31-33秒输出。

   视频直接表达

在 $k=-1024,-1023,\ldots,1024$ 的测试范围内没有发现反例，程序只输出 `**********`。

终端输出中没有任何 $k$ 值，只有循环结束标记 `**********`。

1. 图示
   观察依据

   画面为深色背景的文档页面，标题为“两个数的最大公约数的递推公式”。

2. 图示
   观察依据

   页面依次显示核心公式、1.1 更相减损术、1.2 辗转相除法。

3. 动画
   观察依据

   鼠标在公式附近移动并选中部分文本。