首页 > 代码库 > POJ 2142 The Balance 扩展欧几里得
POJ 2142 The Balance 扩展欧几里得
http://poj.org/problem?id=2142
题意:给出a,b,d<=5e5,问满足x,y>=0,ax+by=d && |x|+|y| 尽量小
x,y都为正表示 a,b在c的另外一边.x,y一正一负表示a,b不在同一边
利用exgcd 求出x,y 另x或者y为最小正整数解,带入方程后求出另一个解,取abs(若为负代表不在同一边)即可
#include <iostream> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <cstdio> #include <map> #include <vector> using namespace std; typedef long long ll; const int N=1e3+20; const int inf=2e8; int a,b,d; int x,y; int gcd(int a,int b) { if(b==0) { x=1,y=0; return a; } ll D=gcd(b,a%b); ll t=y; y=x-a/b*y; x=t; return D; } int main() { while(cin>>a>>b>>d&&(a+b+d)) { int x1,y1; int D=gcd(a,b); x=x*d/D; int t=b/D; //通解 x=x0+t1*i, x带回ax+by=c 求出y x=(x%t+t)%t;//ax+by=c x在左边 y=abs((d-a*x)/b); x1=x,y1=y; D=gcd(b,a); x=x*d/D; t=a/D; x=(x%t+t)%t; y=abs((d-b*x)/a); if(x1+y1<x+y) cout<<x1<<‘ ‘<<y1<<endl; else cout<<y<<‘ ‘<<x<<endl; } return 0; }
POJ 2142 The Balance 扩展欧几里得
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。