本文摘要：该题解主要介绍了如何利用扩展欧几里得算法求解同余方程ax ≡ 1 (mod b)中的最小正整数解x，并将其转化为线性方程形式。通过C++实现，首先调用exgcd函数计算a和b的最大公约数及其满足贝祖定理的一组解，然后对得到的x值进行适当处理以确保其为最小正整数。此外，还涉及了自定义输入处理函数read()的使用以及输出结果的调整。

转载文章

本篇文章为转载内容。原文链接：https://blog.csdn.net/weixin_30590285/article/details/97558051。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

传送门：同余方程

题意不说了很水……学完扩欧做的板子题
把ax≡1(modb)转化成一般线性方程ax+by=1
然后扩欧

唯一要注意的是要找最小正整数解，所以搞出来x之后需要乱搞处理一下
然后就没有了
这是一篇很水的题解……关于扩欧走这里：扩展欧几里得学习笔记

代码：

#include<bits/stdc++.h>
using namespace std;
inline int read(){int cnt=0,f=1;char c;c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c)){cnt=cnt*10+c-'0';c=getchar();}return cnt*f;
}
int a,b,x,y;
void exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);int z=x;x=y;y=z-y*(a/b);
//    return d; 
}
int main(){a=read();b=read();exgcd(a,b,x,y);if(b<0)b=-b;if(x<=0){while(x<0)x+=b;printf("%d",x);}else{while(x>0)x-=b;x+=b; printf("%d",x);}return 0;
}

转载于:https://www.cnblogs.com/kma093/p/10087253.html

本篇文章为转载内容。原文链接：https://blog.csdn.net/weixin_30590285/article/details/97558051。

该文由互联网用户投稿提供，文中观点代表作者本人意见，并不代表本站的立场。

作为信息平台，本站仅提供文章转载服务，并不拥有其所有权，也不对文章内容的真实性、准确性和合法性承担责任。

如发现本文存在侵权、违法、违规或事实不符的情况，请及时联系我们，我们将第一时间进行核实并删除相应内容。

名词解释

作为当前文章的名词解释，仅对当前文章有效。

同余方程：在数论中，同余方程是指形如“ax ≡ b (mod m)”的等式，其中a、b和m是整数，并且m不为0。这意味着当两个整数相除时，它们具有相同的余数。例如，在本题解中提到的“ax ≡ 1 (mod b)”，表示寻找一个整数x，使得ax除以b的余数恒等于1。

扩展欧几里得算法：扩展欧几里得算法是在经典欧几里得算法（用于求解两个非负整数的最大公约数）基础上的一种推广形式。该算法不仅能求出a和b的最大公约数gcd(a, b)，还能同时找到一组整数解x和y，满足贝祖定理 ax + by = gcd(a, b)。在本文中，使用扩展欧几里得算法来解决同余方程，找到最小正整数解。

贝祖定理（Bézout's Identity）：在数论中，贝祖定理指出，对于任何两个非零整数a和b，存在一对整数x和y，使得ax + by等于a和b的最大公约数。这个定理为扩展欧几里得算法提供了理论基础，通过该算法可以得到这样的整数对(x, y)，并在解决同余方程问题时找到符合题目要求的解。

线性方程：线性方程是代数学中最基本的一类方程，其一般形式为ax + by = c，其中a、b和c是常数，而x和y是未知数。在本题解中，将同余方程转化为线性方程ax + by = 1是为了利用扩展欧几里得算法进行求解，因为扩展欧几里得算法适用于解决此类线性组合形式的等式问题。

最小正整数解：在特定数学问题或应用背景下，最小正整数解指的是满足某种条件的最小非负整数值。在处理同余方程时，需要找到满足方程的最小正整数解x，即在所有可能的解中，选择绝对值最小且为正的整数解。在本文讨论的题目中，通过调整扩展欧几里得算法得出的解，确保输出的x为符合条件的最小正整数。