首页 > 代码库 > 扩展gcd求解二元不定方程及其证明
扩展gcd求解二元不定方程及其证明
#include <cstdio> #include <iostream> using namespace std; /*扩展gcd证明 由于当d = gcd(a,b)时; d = d1 = gcd(b,a%b); d1 = b1x1 + a%by1; d = ax+by = b1x1+a%by1。又由于a%b = a - a%b*b; 上式变形能够有 b1x1 + (a-b*a/b)*y1 = a*y1 + b*(x1-a/b*y1); 也就是是说ax+by = a*y1 + b*(x1-a/b*y1); 所以当x=y1,y = x1-a/b*y1时。能够满足有d=ax+by; */ int fun(int a,int b,int d,int &x,int &y){ if(b == 0){ x = 1; y = 0; return a; } else{ d = fun(b,a%b,d,x,y); int t; t = x; x = y; y = t-a/b*y; return d; } } int main(){ int a,b,d; cin >>a >> b >> d; int x,y; fun(a,b,d,x,y); printf("%d %d\n",x,y); return 0; }
扩展gcd求解二元不定方程及其证明
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。