---
title: "（可能要放在拓展欧几里得里）GCD"
created: 2025-11-28
tags:
  - 算法
---

# （可能要放在拓展欧几里得里）GCD

## 题目 [GCD](https://www.acwing.com/problem/content/4662/)

![[image-a296a3e6.png]]

## 思路分析

结论：对于两个变量x和x + a(a为正整数常量， x为正整数域下的变量)， 它们的公约数上界为a 证明如下：

**x和x+a不可能有大于a的公约数**

当x < a时， x不可能存在大于a的约数 当x = a时， x和x+a的最大公约数为a 当x > a 时， 假设x有一约数y，
且y>a。 则(x+a)%y=0+a%y=a≠0， 所以y不可能是x+a的约数。 所以， x和x+a不可能有大于a的公约数

**x和x+a可以取到a为公约数**

当a就是x的约数时， (x+a)%a=0

事实上， x%a=0⟺(x+a)%a=0

所以， 存在情况使得a是x和x+a的公约数

综上， a是x和x+a的公约数上界

回到题目中， 可以发现a + k和b + k两个数的差值是始终不变的， 可以看作是上面的x和x+a 所以问题等价于求最小的k使得 a+k或者b+k是abs(a-b)的倍数即可。

此时求k有两种思考过程, 设m = abs(a -b)。

补余数， a可以表示为a=c∗m+d,d<m，d即为a%m， 所以只需要将d补至模m为0即可，即k=m−d 。但当d为0时， 不需要加k，
因此k可以表示为k=(d==0?0:m−d)

同余式， (a+k)%m=0⟺k≡−a (modm), 所以k即为k=(−a)%m,

但C系语言中， 负数模正数的结果为负数， 所以当k小于0时需要再加一个m，

所以ans=((−a)%m+m)%m 可以发现， 两种推导过程的结果其实是一样的

## 代码实现

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main () {
    ll a, b; cin >> a >> b;
    ll mx = abs(a - b);
    cout << (a % mx == 0 ? 0 : mx - a % mx) << endl;
    //cout << (mx - a % mx) % mx << endl;
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[轻拍牛头|轻拍牛头]] 🏠 [[00-刷题理模型]] ➡️ [[（跳过了 怕了）Hankson的趣味题|（跳过了 怕了）Hankson的趣味题]]