首页 > 编程语言 >对最大公约数求法和扩展欧几里得算法的简要概述

对最大公约数求法和扩展欧几里得算法的简要概述

时间:2024-02-17 15:36:10浏览次数:50  
标签:gcd int 欧几里得 算法 exgcd 求法 最大公约数 ax lcm

目录

1. 最大公约数 (gcd)

数论中,通常用 \(d\ |\ a\) 表示 \(d\) 能整除 \(a\),即 \(d\) 是 \(a\) 的约数,用 \(d\not | \ a\) 表示 \(d\) 不是 \(a\) 的约数。

已知正整数 \(a,b\),如何求 \(g=gcd(a,b)\)?


1.1 更相减损术

  • 若 \(a\geqslant b\),则 \(gcd(a,b)=gcd(b,a-b)\)

证明很简单,因为 \(a,b\) 都是 \(g\) 的倍数,所以设 \(a=k_{1}g,b=k_{2}g\),显然有 \(gcd(k_{1},k_{2})=1\),\(gcd(b,a-b)=gcd(k_{2}g,(k_{1}-k_{2})g)=g\cdot gcd(k_{2}g,(k_{1}-k_{2}))\)。

证明一下 \(gcd(k_{2},(k_{1}-k_{2}))=1\) 即可,可以假设它不为 \(1\) 然后反证,最后肯定能证明等式成立。


如果 \(a\gg b\),更相减损术的时间复杂度会达到最差的 \(O(a)\)

考虑这样一个优化:

如果 \(2\ |\ a,2\ |\ b\),则 \(gcd(a,b)=2\ gcd(\dfrac{a}{2},\dfrac{b}{2})\)

如果仅有 \(2\ |\ a\),\(gcd(a,b)=gcd(\dfrac{a}{2},b)\),仅有 \(2\ |\ b\) 时同理

优化后的算法也叫 Stein 算法

实现:

int gcd(int a, int b) {
    a = abs(a), b = abs(b);
    if (a == 0 || b == 0) return a + b;
    int atimes = 0, btimes = 0;
    while (~a & 1) {
        a >>= 1;
        ++atimes;
    }
    while (~b & 1) {
        b >>= 1;
        ++btimes;
    }
    do {
        while (~a & 1) a >>= 1;
        while (~b & 1) b >>= 1;
        if (a < b) swap(a, b);
        a -= b;
    } while (a);
    return b << min(atimes, btimes);
}

时间复杂度分析

\(2\ |\ a,2\ |\ b\) 时,每次循环会让 \(a,b\) 各减少一半。

否则仅有 \(2\ |\ a\) 或 \(2\ |\ b\),每次循环会让 \(a,b\) 之一减少一半。

否则一定有 \(2\ | (a-b)\)。

综上,时间复杂度是 \(log\) 级别的,至于是 \(log\) 多少,没算,懒得算,总之一定不会超过 \(O(log(a+b))\)。




1.2 辗转相除法 (欧几里得算法)

  • \(gcd(a,b)=gcd(b,a\ mod\ b)\)

证明也很简单:

\(a<b\) 时显然成立

\(a\geqslant b\) 时,不妨设 \(a=qb+r\ (r=a\ mod\ b<b)\),因为 \(a,qb\) 都是 \(g\) 的倍数,所以 \(a-qb=r\) 也是 \(g\) 的倍数,反之亦成立,所以 \(a,b\) 的公约数集合与 \(b,a\ mod\ b\) 相同。

实现:

int gcd(int a, int b) {
    while (b) {  // b = 0 时 gcd(a, b) = a,此时退出循环返回 a 即可
        a %= b;
        swap(a, b);
    }
    return a;
}

或者写成递归形式,用条件运算符一行解决:

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

时间复杂度分析

如果传入的参数是 \(a<b\),只要经过一次循环就变成 \(a>b\),并且后面对 \(b\) 取模时也一定有 \(a>b\)。

当 \(a\geqslant b\),对 \(b\) 取模后 \(a\) 会减小一半以上,所以取模次数是 \(O(log\ a)\) 的。

综上,时间复杂度是 \(O(log(max\{a,b\}))\)。


由于 Stein 算法不涉及取模,相对而言在常数上略占优势,但由于欧几里得算法实现简单,所以后者在竞赛中更常用。




2. 最小公倍数 (lcm)

  • 对任意正整数 \(a,b\),恒有 \(gcd(a,b)\times lcm(a,b)=a\times b\)

证明:

在认为 \(a,b\) 包含相同质因子的前提下对 \(a,b\) 作质因数分解:

\(a=p_{1}^{c_{1}}p_{2}^{c_{2}}...p_{n}^{c_{n}}\)

\(b=p_{1}^{d_{1}}p_{2}^{d_{2}}...p_{n}^{d_{n}}\)

\(gcd(a,b)=p_{1}^{min\{c_{1},d_{1}\}}p_{2}^{min\{c_{2},d_{2}\}}...p_{n}^{min\{c_{n},d_{n}\}}\)

\(lcm(a,b)=p_{1}^{max\{c_{1},d_{1}\}}p_{2}^{max\{c_{2},d_{2}\}}...p_{n}^{max\{c_{n},d_{n}\}}\)

因为 \(min\{c_{i},d_{i}\}+max\{c_{i},d_{i}\}=c_{i}+d_{i}\),所以 \(gcd(a,b)\times lcm(a,b)=a\times b\)

所以只要求出 \(gcd(a,b)\),就能 \(O(1)\) 求出 \(lcm(a,b)\)

实现:

int lcm(int a, int b) { return a / gcd(a, b) * b; }  // 最好像这样先除再乘以免溢出

如果你不想手写这两个函数,C++17 起可以直接用 <numeric> 头文件中的 std::gcdstd::lcm




3. 裴蜀定理 (贝祖定理)

  • 关于 \(x,y\) 的二元一次不定方程 \(ax+by=n\ (a,b,n\in \Z)\) 有整数解的充要条件是 \(gcd(a,b)\ |\ n\)。

证明略。 同学们可以尝试一下它的证明。

贝祖定理可以推广至三元及以上一次不定方程:

  • \(ax+by+cz=n\) 有整数解 \(\lrArr n\ |\ gcd(a,b,c)\ (a,b,c,n\in \Z)\)

3.1 扩展欧几里得算法 (exgcd)

扩展欧几里得算法能在求出 \(gcd(a,b)\) 的同时顺带求出 \(ax+by=gcd(a,b)\) 的一组特解。

还记得如何求递归求 \(gcd(a,b)\) 吗?

  • 递归: 求出 \(gcd(b,a\ mod\ b)\),就相当于求出了 \(gcd(a,b)\)
  • 递归终点: \(b=0,gcd(a,0)=a\)

根据这个递归过程,我们可以考虑这样设计 \(exgcd\) 函数:
\(exgcd(a,b)\) 用于求出满足不定方程 \(ax+by=g\) 的三个整数 \(x,y,g\),其中 \(g=gcd(a,b)\)

  • 递归: 先求出 \(exgcd(b, a\ mod\ b)=(x_{0},y_{0},g)\),考虑如何用它反推出 \(exgcd(a,b)=(x,y,g)\)

    显然有以下等式:

    \(ax+by=bx_{0}+(a\ mod\ b)y_{0}=g\)

    \(ax+by=bx_{0}+(a-\lfloor\dfrac{a}{b}\rfloor b)y_{0}\)

    \(ax+by=ay_{0}+bx_{0}-\lfloor\dfrac{a}{b}\rfloor b y_{0}\)

    \(ax+by=ay_{0}+b(x_{0}-\lfloor\dfrac{a}{b}\rfloor y_{0})\)

    由此得到一组特解: \(x=y_{0},y=(x_{0}-\lfloor\dfrac{a}{b}\rfloor y_{0})\)

  • 递归终点: \(b=0\),解得 \(x=1,y=0,g=a\)

实现:

tuple<int, int, int> exgcd(int a, int b) {
    if (b == 0) return {1, 0, a};
    auto [x0, y0, g] = exgcd(b, a % b);
    int x = y0;
    int y = x0 - a / b * y0;
    return {x, y, g};
}

习题:
abc340_f S = 1

标签:gcd,int,欧几里得,算法,exgcd,求法,最大公约数,ax,lcm
From: https://www.cnblogs.com/xbai2/p/18017994

相关文章

  • 最大公约数和最小公倍数
    一、问题描述P1029[NOIP2001普及组]最大公约数和最小公倍数问题二、问题简析2.1最大公约数求两个正整数的最大公约数gcd(greatestcommondivisor),最常用的方法是辗转相除法。//求a和b的最大公约数intgcd(inta,intb){ if(b==0)returna; returngcd(a,......
  • C语言解题 || 小乐乐与欧几里得
    题目:小乐乐最近在课上学习了如何求两个正整数的最大公约数与最小公倍数,但是他竟然不会求两个正整数的最大公约数与最小公倍数之和,请你帮助他解决这个问题。输入描述:每组输入包含两个正整数n和m。(1≤n≤109,1≤m≤109)输出描述:对于每组输入,输出一个正整数,为n和m的最大公约数......
  • 类欧几里得算法
    模板题:P5170【模板】类欧几里得算法复述题解:我们记\(f(a,b,c,n)=\sum\limits_{i=0}^{n}\Big\lfloor\dfrac{ai+b}{c}\Big\rfloor\,,\g(a,b,c,n)=\sum\limits_{i=0}^{n}i\Big\lfloor\dfrac{ai+b}{c}\Big\rfloor\,,\h(a,b,c,n)=\sum\limits_{i=0}^{n}{\Big\lfloor......
  • P1029 最大公约数和最小公倍数问题
    321上题目链接:P1029[NOIP2001普及组]最大公约数和最小公倍数问题本小蒟蒻的原始思路就是枚举所有范围内的数,分别求出他们的最大公约数和最小公倍数,再看是否满足题意。于是就有了以下一言难尽的东西(;′⌒`)↓#include<stdio.h>intmain(){intx,y,count;sc......
  • 欧几里得算法
    欧几里得算法用于求解两个数\(a,b\)的最大公约数,\(\gcd(a,b)=\gcd(b,a\bmodb)\),为了方便证明,我们约定\(a>b\),证明:设\(r=a\bmodb=a-k\cdotb\),\(d\mida\)且\(d\midb\),显然\(a=k\cdotb+r\),那么\(\frac{r}{d}=\frac{a}{d}-\frac{k\cdot......
  • 求最大公约数
    欧几里得算法基础:设有几个数\(a,b,c\)若\(a|b\)且\(a|c\)则\(a|b+c\)故而我们可以推出\(a|xb+yc\)我们可以推出\((a,b)=(b,a\modb)\)注:()是括号内两个数公约数集合​ |是整除得意思。证明:因为\(a\modb==a-[\fracab]*b\)故而我们根据上述定理。设左边任何一个公约......
  • P1029 [NOIP2001 普及组] 最大公约数和最小公倍数问题
    首先最大公因数和最小公倍数之积等于两个原数的积,这是基本性质然后两个数中,最小也是大于等于最大公因数,最大不超过最小公倍数最暴力的方法是,在这个范围内遍历其中一个数,积除以这个数得到另一个数,然后用辗转相除法进行判断就可以求解。当然,可以缩短范围。缩短范围有两个基本思想......
  • C练习题——打印两个数的最大公约数
    算法一:暴力求解(效率不够)#include<stdio.h>intmain(){inta=0;intb=0;scanf("%d%d",&a,&b);intmin=a<b?a:b;while(1){if((a%min==0)&&(b%min==0))break;......
  • 求两数的最大公约数和最小公倍数的n种方法
    最大公约数:公约数,亦称“公因数”。它是指能同时整除几个整数的数。如果一个整数同时是几个整数的约数,称这个整数为它们的“公约数”;公约数中最大的称为最大公约数。对任意的若干个正整数,1总是它们的公因数。最小公倍数:两个或多个整数公有的倍数中,除0以外最小的一个公倍数。......
  • 求其最大公约数和最小公倍数,一行代码完成
    题目:输入两个正整数m和n,求其最大公约数和最小公倍数。求出最大公约数就行,最小公倍数用m*n除以最大公约数就行packagemyself;importjava.util.Scanner;/***@AutherQY*@Date2023/12/11*/publicclassSix{publicstaticvoidmain(String[]args){......