[原创]POJ 2142 The Balance [不定方程和最小的正整数解]【数论】

2016-09-16 17:15:30 Tabris_ 阅读数：1428

博客爬取于2020-06-14 22:43:17
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52556618

题目链接：http://poj.org/problem?id=2142

--------------------------------------------.

The Balance
Time Limit: 5000MS Memory Limit: 65536K
Total Submissions: 5998 Accepted: 2610
Description

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1). Although she could put four 300mg weights on the medicine side and two 700mg weights on the other (Figure 2), she would not choose this solution because it is less convenient to use more weights.
You are asked to help her by calculating how many weights are required.
这里写图片描述

Input

The input is a sequence of datasets. A dataset is a line containing three positive integers a, b, and d separated by a space. The following relations hold: a != b, a <= 10000, b <= 10000, and d <= 50000. You may assume that it is possible to measure d mg using a combination of a mg and b mg weights. In other words, you need not consider “no solution” cases.
The end of the input is indicated by a line containing three zeros separated by a space. It is not a dataset.
Output

The output should be composed of lines, each corresponding to an input dataset (a, b, d). An output line should contain two nonnegative integers x and y separated by a space. They should satisfy the following three conditions.
You can measure dmg using x many amg weights and y many bmg weights.
The total number of weights (x + y) is the smallest among those pairs of nonnegative integers satisfying the previous condition.
The total mass of weights (ax + by) is the smallest among those pairs of nonnegative integers satisfying the previous two conditions.

No extra characters (e.g. extra spaces) should appear in the output.
Sample Input

700 300 200
500 200 300
500 200 500
275 110 330
275 110 385
648 375 4002
3 1 10000
0 0 0
Sample Output

1 3
1 1
1 0
0 3
1 1
49 74
3333 1
Source

--------------------------.
题目大意 :
就是有一个天平 现在你要称N质量的物体
你只有a,b两种质量的砝码若干
问你最少需要每种砝码多少个才能称出N质量的物体
(要求在个数相同的时候选取砝码质量和最少的组合)

解题思路:
这道题目其实很简单 打眼一瞅就知道是一个扩展欧几里得

但是对于怎么输出最小的解得组合 这点就不太容易了

其实呢也不难 稍加分析就能得到结果了
首先呢
运用扩展欧几里得能够求出x,y的任意一组解
这样的话 假如求x或y的最小正整数解释非常容易的
只要x=(x%a+a)%a y=(x%b+b)%b这样就行了
然后想 要求出|x|+|y|的最小值怎么办呢
其实无非是两种
一种是在x为最小正整数解的时候
另一种是在y为最小正整数解的时候
证明略(取数是稍微想一想就知道了)

知道这个就好了

最后把两种的结果一比较 就能得出符合题意的解了

附本题代码
------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# include <vector>
# include <queue>
# include <set>
# include <map>
# include <string>
# include <math.h>
# include <stdlib.h>
# include <time.h>
using namespace std;
typedef long long int LL ;
# define INF 0x3f3f3f3f
# define pb push_back
# define abs(a) (a)>0?(a):-(a)
# define lalal puts("*******");
/*************************************/
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b)
    {
        x=1,y=0;
        return a;
    }
    else
    {
        LL r = exgcd(b,a%b,x,y);
        LL t = x;
        x = y;
        y = t-(a/b)*y;
        return r;
    }
}

int main()
{
    int a,b,d;
    while(~scanf("%d%d%d",&a,&b,&d)&&(a||b||d))
    {

        LL x,y,vx,vy;

        LL r = exgcd(a,b,x,y);  //本题让求最小解
        a/=r,b/=r,d/=r;

        exgcd(a,b,x,y);

        /********** 1 令y是最小正整数解**********/
        vy = y*d;
        vy = (vy % a + a) % a;
        vx = (d-b*vy) / a;
        vx = abs(vx);
        /********** 2 令x是最小正整数解**********/
        x *= d;
        x = (x % b + b) % b;
        y = (d-a*x) / b;         //同理
        y = abs(y);
        /********** 3 使得和最小**********/
        if(x+y<vx+vy)    vx=x,vy=y;


        printf("%I64d %I64d\n",abs(vx),abs(vy));
    }
    return 0;
}