1. 全栈程序员必看首页

裴蜀定理 【浅讲】

全栈程序员-站长 • • 未分类 • 阅读 2

裴蜀定理 【浅讲】这里证明不会讲解 因为写这篇文章的目的是为了让大家简单理解裴蜀定理 以及可以在算法题中可以运用 主要针对于做题 裴蜀定理 又称贝祖定理 特殊性 对于方程 ax by 1 只有整数 a 和 b 互质时 方程才有整数解 裴蜀定理的证明视频裴蜀定理的证明文章扩展欧几里德算法是用来在已知 a b 求解一组 x y 使它们满足裴蜀 贝祖 等式 ax by gcd a b d 扩展欧几里得算法 exgcd877 扩展欧几里得算法 https www a

裴蜀定理(又称贝祖定理)
在这里插入图片描述
特殊性: 对于方程ax+by=1只有整数a和b互质时，方程才有整数解。




扩展欧几里德算法是用来在已知a , b 求解一组x , y ，使它们满足裴蜀（贝祖）等式： a x + b y = gcd ⁡ ( a , b ) = d


扩展欧几里得算法——exgcd

877. 扩展欧几里得算法
在这里插入图片描述
https://www.acwing.com/problem/content/description/879/
在这里插入图片描述






#include 
     #include 
     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); y=y-a/b*x; return d; } int main(void) { 
    int t; cin>>t; while(t--) { 
    int a,b,x,y; cin>>a>>b; exgcd(a,b,x,y); cout<<x<<" "<<y<<endl; } return 0; } 
#include 
     using namespace std; int exgcd(int a,int b,int& x,int& y) { 
    if(!b) return x=1,y=0,a; int d=exgcd(b,a%b,y,x); y=y-a/b*x; return d; } int main(void) { 
    int n; cin>>n; while(n--) { 
    int a,b,x,y; cin>>a>>b; exgcd(a,b,x,y); cout<<x<<" "<<y<<endl; } return 0; }

878. 线性同余方程

在这里插入图片描述
https://www.acwing.com/problem/content/880/
在这里插入图片描述
这不就是裴蜀定理么？ 我们知道1可以用扩展的欧几里得来求解。如同上面的是一样。
但是我们这里是 b。 我们可以先求 ax+my=gcd(a,m) 最后在乘以一个倍数就可以了。








#include 
     #include 
     #include 
     using namespace std; typedef long long int LL; LL exgcd(LL a,LL b,LL &x,LL &y) { 
    if(!b){ 
    x=1,y=0; return a; } int d=exgcd(b,a%b,y,x); y=y-a/b*x; return d; } int main(void) { 
    int t; cin>>t; while(t--) { 
    LL a,b,m; cin>>a>>b>>m; LL x,y,d; d=exgcd(a,m,x,y); if(b%d) cout<<"impossible"<<endl; else cout<<x*b/d%m<<endl; } return 0; } 
#include 
     using namespace std; typedef long long int LL; LL exgcd(LL a,LL b,LL &x,LL &y) { 
    if(!b) return x=1,y=0,a; int d=exgcd(b,a%b,y,x); y=y-a/b*x; return d; } int main(void) { 
    int n; cin>>n; while(n--) { 
    LL a,b,m,x,y,d; cin>>a>>b>>m; d=exgcd(a,m,x,y); if(b%d) puts("impossible"); else cout<<x*b/d%m<<endl; } return 0; }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/216637.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月18日 上午11:25
下一篇 2026年3月18日 上午11:25


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号