Java教程

数论(六)——扩展欧几里得算法

本文主要是介绍数论(六)——扩展欧几里得算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

  • 欧几里得算法
  • 裴蜀定理
  • 扩展欧几里得算法
  • 线性同余方程

欧几里得算法

欧几里得算法,即辗转相除法,是指用于计算两个非负整数a,b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
核心原理gcd(a,b) = gcd(b,a mod b)
一个基本的性质:d | a,d | b,d | (a+b),d | (ax + by)
(d能整除a,d能整除b,那么d就能整除a+b,也能整除a的若干倍+b的若干倍)

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

b不为0时,最大公约数是gcd(b, a mod b)
b为0时,最大公约数就是a(0可以整除任何数)


裴蜀定理

在学习扩展欧几里得算法之前,先来简单了解一下裴蜀定理
内容:对于任意正整数a,b,那么一定存在非零整数x,y,使得
ax + by = (a,b) (a和b的最大公约数)
ax + by = d (d为a和b的最大公约数的倍数)
显然,凡是能由a和b凑出来的数,一定是a和b最大公约数的倍数,而其中最小的正整数就是a和b的最大公约数。
扩展欧几里得是一个算法,它能够在已知任意正整数a和b的前提下,都可以求出符合上述条件的x,y。


扩展欧几里得算法

给定 n 对正整数 ai,bi,对于每对数,求出一组 xi,yi,使其满足 ai×xi+bi×yi=gcd(ai,bi)。
思路
1.当 b = 0 时,a和b的最大公约数就是a,所以有ax + 0y = a,显然 x = 1,y = 0 就是一组解

2.当 b ≠ 0 时,
已知 ,gcd(a,b) = gcd(b,a % b)
递归结束后,就有 by + (a mod b)x = (a,b) = d
a mod b = a - ⌊a/b⌋·b

by + (a % b)x = gcd(b,a % b)

by + (a - ⌊a / b⌋ * b)x = gcd(b,a % b)

ax+ b(y- ⌊a / b⌋ * x) = gcd(b,a % b) = gcd(a,b) = ax + by

所以,x = x ,y = y - ⌊a / b⌋ * x

#include <iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b) 
    {
        x = 1, y = 0;
        return a;
    }
    
    int d =  exgcd(b,a % b,y,x);
    //b和a%b的系数分别为y和x
    
    y -= a/b * x;
    
    return d;
}
int main()
{
    int n;
    scanf("%d",&n);
    
    while(n -- )
    {
        int a,b,x,y;
        scanf("%d %d",&a,&b);
        
        exgcd(a,b,x,y);
        
        printf("%d %d\n",x,y);
    }
}

线性同余方程

给定 n 组数据 ai,bi,mi,对于每组数求出一个 xi,使其满足 ai×xi≡bi(mod mi),如果无解则输出 impossible。
考点:扩展欧几里得算法的应用
分析:
a×x≡b(mod m) 等价于 存在一个整数y 使得 ax = my + b,即 ax - my = b,
ax + my = b (y = -y),这样就转换成了扩展欧几里得算法能够求解的形式,由扩展欧几里得算法可以求出 ax + my = gcd(a,b) 的解,那么怎么 ax + my = b 的解呢,很简单ax + my = gcd(a,b) 等式两边同乘 b / gcd(a,b) 即可前面提到过,此方程有解的充要条件是 (a,m) | b

#include <iostream>

using namespace std;

int exgcd(int a,int b,int &x,int &y)
{
    if(!b) 
    {
        x = 1, y = 0;
        return a;
    }
    
    int d =  exgcd(b,a % b,y,x);
    //b和a%b的系数分别为y和x
    
    y -= a/b * x;
    
    return d;
}
int main()
{
    int n;
    scanf("%d",&n);
    
    while(n -- )
    {
        int a,b,m;
        scanf("%d %d %d",&a,&b,&m);
        int x,y;
        int d = exgcd(a,m,x,y);
        
        if(b % d) puts("impossible"); //b不是(a,b)的倍数
        else
        printf("%d\n",(long long)x * b/d % m);
    }
    
    return 0;
}
这篇关于数论(六)——扩展欧几里得算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!