问题分析

这是一个关于使用两种不同重量的砝码（a毫克和b毫克）来称量特定重量d毫克药物的问题。题目要求：

• 只能使用两种固定重量的砝码（a和b）
• 砝码可以放在天平的两侧（药物侧或砝码侧）
• 需要找到使用最少砝码数量的解
• 在砝码数量相同的情况下，选择总重量更小的解

解题思路

数学建模

该问题可以转化为求解线性丢番图方程：

a*x - b*y = d   或   b*y - a*x = d

其中x和y都是非负整数，分别表示两种砝码的使用数量。

解决步骤

1. 使用扩展欧几里得算法：

   • 找到方程 aX + bY = gcd(a,b) 的特解
   • 通过特解构造原方程的解

2. 寻找非负整数解：

   • 计算通解形式
   • 确定参数k的范围使得x和y都为非负数

3. 选择最优解：

   • 比较所有可能的非负解
   • 优先选择x+y最小的解
   • 当x+y相同时，选择ax + by更小的解

标程

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;

#define N 100001
#define maxn 1005
typedef long long ll;

int exgcd(int a,int b,int &x,int &y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int q=exgcd(b,a%b,x,y);
    int t=x;
    x=y;
    y=t-a/b*y;
    return q;
}

int main(){
    int a,b,d,p,q,x,y;
    while(~scanf("%d%d%d",&a,&b,&d)){
        if(a==0&&b==0&&d==0) return 0;
        int md=exgcd(a,b,x,y);
        a/=md,b/=md,d/=md;
        int x1=x*d;
        x1=(x1%b+b)%b;
        int y1=(d-a*x1)/b;
        y1=abs(y1);
        int y2=y*d;
        y2=(y2%a+a)%a;
        int x2=(d-b*y2)/a;
        x2=abs(x2);
        if(x1+y1<x2+y2) printf("%d %d\n",x1,y1);
        else printf("%d %d\n",x2,y2);
    }
    return 0;
}