题意：给你两个砝码的质量A,B。称量一个鬼东东的质量为K，问最少要多少砝码。
题解：易得出
Ax-By=K，用扩展欧几里德算法去元，求出x，y。
求出x,y然后分成两组,求出x可以根据方程推出y，求出y可以根据方程推出x.然后取两组相加的最小值即可.
代码：
1 #include <stdio.h> 2 #include <iostream> 3 #include <algorithm> 4 #include <sstream> 5 #include <stdlib.h> 6 #include <string.h> 7 #include <limits.h> 8 #include <string> 9 #include <time.h> 10 #include <math.h> 11 #include <queue> 12 #include <stack> 13 #include <map> 14 using namespace std; 15 typedef long long ll; 16 17 ll gcd(ll a,ll b){ 18 if(b==0) return a; 19 return gcd(b,a % b); 20 } 21 22 void ggcd(ll a,ll b,ll &x,ll &y){ 23 if (b==1){ 24 x=1; y=1-a; 25 } else{ 26 ll x1,y1; 27 ggcd(b,a%b,x1,y1); 28 x=y1; y=x1-x*(a/b); 29 } 30 } 31 32 int main(){ 33 ll n,m,k; 34 cin>>n>>m>>k; 35 while (n||m||k) 36 { 37 ll g=gcd(n,m); 38 ll x,y,y1,x1; 39 n/=g; m/=g; 40 ggcd(n,m,x,y); 41 x1=x*k/g; 42 x1=(x1%m+m)%m; 43 y1=(k/g-n*x1)/m; 44 if (y1<0) y1=-y1; 45 46 y=y*k/g; 47 y=(y%n+n)%n; 48 x=(k/g-m*y)/n; 49 if (x<0) x=-x; 50 if (x+y>x1+y1) { 51 x=x1; y=y1; 52 } 53 cout<<x<<" "<<y<<endl; 54 cin>>n>>m>>k; 55 } 56 return 0; 57 }