欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[扩展欧拉函数] POJ2142The Balance

程序员文章站 2022-07-03 09:10:41
题目有两种砝码a,b,要用ab称出c的质量,计算ab的最少个数题目链接:http://poj.org/problem?id=2142思路还没学LaTeX代码#include#include#include#include#include#include#include#includ...

题目

[扩展欧拉函数] POJ2142The Balance
有两种砝码a,b,要用ab称出c的质量,计算ab的最少个数
题目链接:http://poj.org/problem?id=2142

思路

还没学LaTeX
[扩展欧拉函数] POJ2142The Balance

代码

#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