[扩展欧拉函数] POJ2142The Balance

题目

有两种砝码a,b，要用ab称出c的质量，计算ab的最少个数
题目链接：http://poj.org/problem?id=2142

思路

还没学LaTeX

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,x,y);
	int temp=x;
	x=y;
	y=temp-(a/b)*y;
	return g;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int a,b,c;
	while(cin>>a>>b>>c){
		if(a==0&&b==0&&c==0) break;
		bool flag=0;
		if(a<b){
			swap(a,b);
			flag=1;
		}
		int x,y;
		int gcd=exgcd(a,b,x,y);
		c/=gcd,a/=gcd,b/=gcd;
		y*=c,x*=c;
		int t=y/a;
		int minn=INF;
		int res1=0,res2=0;		
		for(int i=t-1;i<=t+1;i++){
			int xx=abs(x+i*b);
			int yy=abs(y-i*a);
			//cout<<xx<<" "<<yy<<endl; 
			if(xx+yy<minn){
				minn=xx+yy;
				res1=xx,res2=yy;
			}
		}
		if(flag) cout<<res2<<" "<<res1<<endl;
		else cout<<res1<<" "<<res2<<endl;
	}
    return 0;
}

本文地址：https://blog.csdn.net/kosf_/article/details/107419101