首页 > 编程语言 >拓展欧几里得算法

拓展欧几里得算法

时间:2024-03-13 15:47:28浏览次数:25  
标签:frac gcd text 欧几里得 拓展 算法 ax ll extgcd

一、拓展欧几里得算法

1.1 算法简析

根据裴蜀定理,对任意 \(a\) 和 \(b\),一定存在 \(x\) 和 \(y\),使 \(ax + by = \text{gcd}(a, b)\)。拓展欧几里得算法不仅能求出 \(a\) 和 \(b\) 的最大公约数,而且能找到一对 \((x, y)\) 使该方程成立。

设求解 \(ax + by = \text{gcd}(a, b)\) 的函数为

int extgcd(int a, int b, int &x, int &y)

该函数返回 \(\text{gcd}(a, b)\),即 \(a\) 和 \(b\) 的最大公约数。同时,引用的 \(x\) 和 \(y\) 就是方程的一对解。

假设 \(b \neq 0\),
\(\text{extgcd(a, b, x, y)}\) 表示的方程为 \(ax + by = \text{gcd}(a, b)\)
\(\text{extgcd(b, a \% b, x', y')}\) 表示的方程为 \(bx' + (a~\%~b)y' = \text{gcd}(b, a~\%~b)\)

我们知道 \(a~\%~b\) 是取余运算,可以转换成 \(a~\%~b = a - \lfloor \frac{a}{b} \rfloor \times b\),代入方程得到 \(bx' + (a - \lfloor \frac{a}{b} \rfloor \times b)y' = \text{gcd}(b, a~\%~b)\),整理得到 \(ay' + b(x' - \lfloor \frac{a}{b} \rfloor \times y') = \text{gcd}(b, a~\%~b)\)

\[\begin{split} &\because b \neq 0 \\ &\therefore \text{gcd}(a, b) == \text{gcd}(b, a~\%~b) \\ &\therefore 两个方程的左式是相等的 \\ \\ &ax + by = ay' + b(x' - \lfloor \frac{a}{b} \rfloor \times y') \\ &\therefore x=y',~y=x' - \lfloor \frac{a}{b} \rfloor \times y' \end{split} \]

假设 \(b == 0\),
\(\text{extgcd(a, b, x, y)}\) 表示的方程为 \(ax = \text{gcd}(a, 0) = a\),可以得到特解 \(x=1,~y=0\)。

因此,我们可以采用递归的方式定义函数。

1.2 模板

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

1.3 通解

\(\text{extgcd(a, b, x, y)}\) 可以得到 \((x_0, y_0)\) 这一个特解,通解为

\[x=x_0+k\frac{b}{\text{gcd}(a,b)},~y=y_0-k\frac{a}{\text{gcd}(a,b)} \]


二、相关题目

2.1 题目描述

P1082 [NOIP2012 提高组] 同余方程

2.2 问题简析

题目要求 \(ax \equiv 1~(\text{mod}~b)\) 的最小正整数解。因为拓展欧几里得算法求解方程的格式为 \(ax + by = \text{gcd}(a, b)\),所以要对原式进行转化。

\[\begin{split} &\because by \equiv 0~(\text{mod}~b)\\ &\therefore ax+by \equiv 1~(\text{mod}~b) \\ \\ &令~ax+by=1\\ 由裴蜀定理&,若该方程有解,则~\text{gcd}(a, b) = 1\\ \\ \therefore~求~ax+by&=\text{gcd}(a, b)~成立的最小正整数~x \end{split} \]

至此,我们可以直接套用上文的模板求解。需要注意的是,本题要求的是 \(x\) 的最小正整数解,所以求出 \(x_0\) 后要进行处理:

x = (x % b + b) % b;

2.3 AC代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a, b, x, y;

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

int main()
{
	cin >> a >> b;
	extgcd(a, b, x, y);
	cout << (x % b + b) % b << endl;
	
	return 0;	
}

标签:frac,gcd,text,欧几里得,拓展,算法,ax,ll,extgcd
From: https://www.cnblogs.com/hoyd/p/18070761

相关文章

  • 【算法】【线性表】【数组】从中序与后序遍历序列构造二叉树
    1 题目给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。示例1:输入:inorder=[9,3,15,20,7],postorder=[9,15,7,20,3]输出:[3,9,20,null,null,15,7]示例2:输入:inor......
  • 4.13 ACM-ICPC算法 字符串之后缀自动机
    4.13ACM-ICPC算法:字符串之后缀自动机在竞赛编程,尤其是ACM-ICPC竞赛中,字符串算法占据了极其重要的位置。其中,后缀自动机(SuffixAutomaton,简称SAM)以其强大的功能和高效的性能,成为了解决字符串问题的利器。本文旨在介绍后缀自动机的基本概念、构建方法以及在算法竞赛中的应......
  • 数据结构与算法学习(01)交换函数的指针陷阱
    先看以下正确的例子 voidswap(int*px,int*py){inttemp;temp=*px;/*间接取*/*px=*py; /*间接取,间接存*/*py=temp; /*间接存*/}int main(void){inta=2,b=3;swap(&a,&b);printf("a=%d,b=%d",a,b);return......
  • 数据结构算法系列----背包问题(01,完全,多重)
    一、01背包1、01背包介绍    "01背包"是一个经典的动态规划问题。在01背包中,给定一个背包容量和一组物品,每个物品都有自己的重量和价值。问题的目标是选择一些物品放入背包中,使得放入的物品总重量不超过背包容量,同时使得放入的物品总价值最大。    "01"表......
  • 数据结构算法系列----快速幂
    一、快速幂的介绍:1、为什么要使用快速幂:   当我们计算a的n次幂时,最先想到的肯定是c中的内置函数  pow(a,n),这个内置函数虽然简单方便,但是在实际使用中这个函数的时间复杂度是o(n),因为它是将a乘n次得到的答案。  由于在n非常大时用pow()很容易超时,因此我们引入一个时......
  • Offer必备算法13_路径dp_六道力扣题详解(由易到难)
    目录①力扣62.不同路径解析代码②力扣63.不同路径II解析代码③力扣LCR166.珠宝的最高价值解析代码④力扣931.下降路径最小和解析代码⑤力扣64.最小路径和解析代码⑥力扣174.地下城游戏解析代码本篇完。①力扣62.不同路径62.不同路径难度中等一个......
  • 算法入门书籍(二)--2024.03.13
    小学C++编程入门书籍及相关资料介绍(二)算法篇小学C++编程入门书籍及相关资料介绍(二)算法篇_c++教材-CSDN博客 算法入门书籍--2022.04.04算法入门书籍--2022.04.04-CSDN博客1、聪明人的游戏信息学探秘.提高篇-2017年06月2、啊哈!算法3、哇,编程!——跟小明一起学......
  • 3.1_4 动态分区分配算法
    3.1_4动态分区分配算法  动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配?(一)首次适应算法算法思想  每次都从低地址开始查找,找到第一个能满足大小的空闲分区。如何实现  空闲分区以地址递增的次序排列。每次分配......
  • 某数4代——某房地产为例扣算法
      提示:本文章仅供学习交流,严禁用于非法用途,如有不当可联系本人删除!文章于2024-3-13发布  网站:aHR0cDovL3d3dy5mYW5nZGkuY29tLmNuL25ld19ob3VzZS9uZXdfaG91c2UuaHRtbA==  过rs4的方法大致有两种,一种是补环境,另一种就是扣算法,我们这里以扣算法的方式来过rs4。一、rs4的响应......
  • 《算法竞赛入门经典 第2版》 数学题目集
    例题10-1巨大的斐波那契数!(ColossalFibonacciNumbers!,UVa11582)巨大的斐波那契数!ColossalFibonacciNumbers!-洛谷例题10-2不爽的裁判(DisgruntledJudge,NWERC2008,UVa12169)不爽的裁判DisgruntledJudge-洛谷NOI数学学习相关书籍及视频等资料(不包......