算法笔记3

2023/7/24 算法笔记数论算法数学最大公约数

数论基础

1. 欧几里得算法

又称辗转相除法

最大公约数简称gcd：Greatest Common Divisor

公式：gcd(a, b) = gcd(b, a mod b)

当b == 0时，a即为结果

如果gcd(a, b) == 1，则a与b互质

一般情况，默认参数a，b要为正数，gcd(a, b)也为正数

虽然数学上，通常规定gcd(-|a|, b) = gcd(|a|, b)

但是用欧几里得算法递归求gcd，若参数为负，则结果也可能为负，而且等于 -gcd(|a|, |b|)，对于结果可能需要处理（取模，参考后面P1516 青蛙的约会解析）

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

2. 最大公倍数

简称：lcm：Least Common Multiple

**公式：gcd(a, b) * lcm(a, b) = a*b**

即 lcm(a, b) = gcd(a, b)/a * b

3. 扩展欧几里得算法

裴蜀定理:

a, b, c为整数，gcd(a, b)

方程 ax+by = c 有解的充要条件为， gcd(a, b) | c ，即gcd(a, b) 为c的因数

ax + by = 1 有解当且仅当整数a和b互素

扩展欧几里得算法：

求解方程 ax+by = gcd(a, b)

可以求出一组特解(递归结束后的x与y)

整个求特解的证明：

ax+by = gcd(a, b) .....①

bx+(a%b)y = gcd(b, a%b) .....②

显然gcd(a, b) = gcd(b, a%b)

所以ax+by = bx+(a%b)y

a%b 可以写成 a - a/b*b 这里的除号是整除，因此a/b要看成整体，所以后面合并时提取的是b，而不是a

ax+by = bx+(a - a/b*b)y

展开ax + by = bx + ay - b*(a/b)y

移向合并ax + by = ay + b(x - (a/b)*y)

因为a，b已知，所以左右对应相等

x = y

y = x - (a/b)*y

显然右边的x和y是递归的下一次的x和y （从前面②式是①式的下一步递归可知）

因此先递归，然后由下一次的x，y值，对本次的x，y赋值

递归会一直先递归到最深处，再回溯，而且肯定会递归到b == 0，此时ax = a，所以x = 1，y可以任取，但一般取0

然后由特解，就能通过它求出该方程的通解，最后还可以求出等式右边为C（满足C % gcd(a, b) = 0）的通解

long long typedef ll;

ll exgcd(ll a, ll b, ll &x, ll &y){
    //从这个最深处，向上回溯
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    //先递归，就能得到下一次递归后的x，y的值
    ll res = exgcd(b, a % b, x, y);
    //得到下一次的值后，进行赋值
    ll t = x;
    x = y;
    y = t - (a / b) * y;
    return res;
}

//比如
int x, y;
cout << exgcd(121, 22, x, y)<<endl; //返回的是gcd结果11
cout << x << "  " << y; //x，y即一组特解，1与-5，因为121*1 + 22*(-5) =  11

已经得到特解和

1.求 ax+by = gcd(a, b) 的通解

推出-->

两边同时除以 gcd(a, b) -->

和互质

说明是的倍数

则有通解

2.求 ax+by = c 条件gcd(a, b) | c 的通解

（如果c % gcd(a, b) != 0 说明无解）

2.1 因为已知ax+by = gcd(a, b) 的通解x，y，直接两边同时乘以 c/gcd(a,b) ,

则x = c/gcd(a,b) * x (右边的x是前面算出来的通解)

如果直接带进去，会导致结果复杂一些，不建议这样

2.2 所以这里使用，不同于前面，这里使用ax+by = gcd(a, b) 的特解

变形（变出c）： * * + * *

建议将这个像之前一样处理，整体当成一个特解

推出-->

带入得 ax+by = c 条件gcd(a, b) | c 的通解

这样通过特解得到的通解，形式比使用前面第一步的通解来得到更简洁

练习：P1516 青蛙的约会

具体思路：可以推出：

y - x = [k(m - n)] % L (k表示次数，L表示总长)

然后推出 y - x = k(m - n) + t * L

令S = y-x，a = m-n，b = L

则有 a * k + b * t = S

就是前面的 ax+by = c

结果就是要，求出最小的正整数k（因为表示跳跃次数）

也就是套用公式，求解a * k + b * t = S的通解，然后求最小正整数

当然无解的充要条件为，S % gcd(a,b) != 0

使用前面的思路，可以解决，但要注意负数的问题，根据范围可知b为正数，但a可能为负数

可以采取下面所写的注释，选择两个方法之一解决（否则只能AC 80%）

还有就是一个技巧，形如 y = kx + b 若k不定，x，b已知，则y的最小正整数为 (b % x + x) % x

比如这个题的通解为：

t未知，其他已知，令 mod = b/gcd(a,b)

x的最小正整数即( % mod + mod ) % mod

#include<bits/stdc++.h>
using namespace std;

long long typedef ll;

ll exgcd(ll a, ll b, ll &x, ll &y){
    if(b == 0){
        x = 1;
        y = 0;
        return a;
    }
    ll res = exgcd(b, a % b, x, y);
    ll t = x;
    x = y;
    y = t - (a / b) * y;
    return res;
}

int main(){
    ios::sync_with_stdio(0);

    ll x, y, t1, t2, t3, t4, t5;
    cin >> t1 >> t2 >> t3 >> t4 >> t5;
    ll a = t3 - t4, b = t5;
    ll S = t2 - t1;
    //方法1，可以通过这样保证gcd方法的参数a为正数（a取相反数，S也要取相反数，才能等式成立，t相当于也会变相反数，但用不到）
    // if(a < 0){
    //     a = -a;
    //     S = -S;
    // }

    ll gcd = exgcd(a, b, x, y);
    if(S % gcd == 0){
        ll mod = b / gcd;
        ll res = ((S / gcd * x) % mod + mod) % mod;
        //方法2，不保证gcd方法参数a为正，得到的gcd可能为最大负数，必须减去一个b/gcd，就变成最小正数
        if(res < 0) res-= mod;
        cout << res;
    }else
        cout << "Impossible";
    return 0;
}

LOADING

算法笔记3

数论基础

1. 欧几里得算法

2. 最大公倍数

3. 扩展欧几里得算法