exgcd怎么求最小正整数解?
  • 板块学术版
  • 楼主Hanghang
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/2/1 22:58
  • 上次更新2023/11/5 03:58:36
查看原帖
exgcd怎么求最小正整数解?
178992
Hanghang楼主2021/2/1 22:58
#include<bits/stdc++.h>
using namespace std;

long long E(long long a,long long b,long long &x,long long &y)
{
	long long d,t;
	if(b==0)
	{
		x=1;y=0;return a;
	}
	d=E(b,a%b,x,y);t=x-a/b*y;
	x=y;y=t;
	return d;
}
int main()
{
	long long a,b,c,x,y,d;
	cin>>a>>b>>c;
	d=E(a,b,x,y);
	cout<<a<<"*"<<x*c/d<<"+"<<b<<"*"<<y*c/d<<"="<<c<<endl;
	return 0; 
}

求助各位大佬,万分感谢

2021/2/1 22:58
加载中...