POJ2142 The Balance

タイトル転送ゲート:http://bailian.openjudge.cn/practice/2142/【題目大意】1つの天秤と、質量aとbの分銅があり、分銅の数に制限がなく、天秤の左右に分銅を置くことができることが知られており、天秤に質量cと呼ばれるものを量ることが要求されている.2つの分銅は両側を分けても同じ側に置いてもいいです.実行可能なシナリオを求めます.要求:置く分銅の数はできるだけ少ない.分銅の数が同じである場合、総質量はできるだけ小さくする.【分析】:与えられたa,b,cはax+by=cを満たす命令|x|+|y|最小(等しい場合、a|x|+b|y|最小)を見つけ、a>bが先に拡張ユークリッドアルゴリズムでx 0を求めることが望ましい.y 0,通解はx=x 0+b/dと表すことができる×t ,y=y0-a/d ×t,|x|+|y|=|x0+b/d ×t |+|y0-a/d × t|このtに関する関数の最小値はt=y 0である×d/a付近の2時ちょうどに取ります.だからこの2点を直接検証すればいいです.なぜなら、a>bを設定した後、|x 0+b/d× t|単調増分、|y 0-a/d×t|まず減少してから増加する.傾きa/d>b/dのため.a>bのため、減少した傾き>増加した傾きであるため、関数には必ずゼロ点があるので、合計|x 0+b/d×t |+|y0-a/d×t|y 0-a/d×t 0=0のt 0付近に最小値がある.コードは次のとおりです.

#include 
using namespace std;
typedef long long LL;
int c;
LL exgcd(LL  a,LL b,LL &x,LL &y){
	if(b == 0){
		x = 1,y = 0;
		return a;
	}
	LL d = exgcd(b,a%b,x,y);
	LL t = x;
	x = y;
	y = t - (a/b)*y;
	return d;
}
int main()
{
    while(1){
    	LL a,b,x,y;
    	cin >> a >> b >> c;
    	if(a == 0 && b==0 && c ==0) break;
    	bool flag = false;
    	if(a < b) { swap(a,b); flag = true;}
    	LL d = exgcd(a,b,x,y);
    	x = x * (c/d); y = y * (c/d);
    	//z = |x|+|y| = |x0 + (b/d) * t| + |y0 - (a/d) * t|    ， |y0-(a/d)*t| = 0     。 
    	LL t = y /(a/d);
    	long long addxy= INT_MAX; 
    	LL ansx ,ansy;
		for(int i = -1;i<2; i++){
    		LL ax = abs(x + (b/d) * (t+i));
    		LL ay = abs(y - (a/d) * (t+i));
    		if(ax + ay < addxy ||(ax + ay == ansx + ansy&& ax * a + ay * b < ansx *a + ansy * b)){
    			addxy = ax + ay;
				ansx = ax;
    			ansy = ay;
    		}
    	}
    	if(flag) swap(ansx , ansy);
    	cout << ansx <