Jams 倒酒 (pour. cpp)

Jams 是一家酒吧的老板, 他的酒吧提供 2 种体积的啤酒, a ml 和 b ml, 分别使用容积为 a ml 和 b ml 的酒杯来装载. 酒吧的生意并不好. Jams 发现酒鬼们都很穷, 不像他那么土豪. 有时, 他们会因为负担不起 a ml 或者 b ml 酒的消费, 而不得不离去. 因此, Jams 决定出手第三种体积的啤酒 (较小体积的啤酒). Jams 只有两种杯子, 容积分别为 a ml 和 b ml, 而且啤酒杯是没有刻度的. 他只能通过两种杯子和酒桶间的互相倾倒来得到新的体积的酒.

倒酒步骤为:

  1. 规定 a>=b
  2. 酒桶容积无限, 酒桶中酒体积无限大.
  3. 只能包含三种可能的倒酒操作:
    1. 将酒桶中的酒倒入容积为 b ml 的酒杯中;
    2. 将容积为 a ml 的酒杯中的酒倒入酒桶;
    3. 将容积为 b ml 的酒杯中的酒倒入容积为 a ml 的酒杯中.
  4. 每次倒酒必须把杯子倒满或者把被倾倒的杯子倒空.

Jams 希望通过若干次倾倒得到容积为 a ml 酒杯中剩下的就体积尽可能小, 他请求你帮助他设计倾倒方案.

输入

两个整数 a, b (\(0 \lt b \leq a \leq 10^9\))

输出

第一行一个整数, 表示可以得到的最小体积的酒.

第二行两个整数 Pa 和 Pb (中间用一个空格分开), 分别表示从体积为 a ml 的酒杯中到处酒的次数和将酒倒入体积为 b ml 的酒杯的次数.

若有多种可能的 Pa, Pb 满足要求, 那么请输出 Pa 最小的. 若 Pa 最小的时候有多个 Pb, 那么输出 Pb 最小的.

样例输入

5 3

样例输出

1
1 2

样例解释

倾倒方案为:

  1. 桶->B;
  2. B->A;
  3. 桶->B;
  4. B->A;
  5. A->桶;
  6. B->A;

数据范围

对于 20% 的数据,\(p_a\),\(p_b\) 总和不超过 5 对于 60% 的数据,\(p_a \leq 10^8\) 对于 100% 的数据,\(0 < b \leq a \leq 10^9\)

Explanation

就是一道结论题, 用一些很漂亮的结论可以解出这一道题.

比如说,\(a, b\) 各除以 \(gcd(a, b)\) 之后得到的数一定互质 (废话). 然后 \(a\ mod\ n \times b, n \in [1, b]\) 所构成的集合 \(S\) 一定满足这样的条件:\(S = {0, 1, 2, ..., b - 1}\), 也就是构成一个剩余系. 这样我们就可 以说明首先最后的答案一定是 \(gcd(a, b)\). 然后我们寻找这样的方法:

无非就是将 A 倒空, 然后不停地用 B 罐装满 A 罐. 直到装满为止倒空 A 罐, 然后再将 剩余的 B 罐中的酒倒到 A 罐里, 以此类推.

然后几个特判:

  1. \(a\ mod\ b = 0\)
  2. \(a = b\)

最后我不是太懂第十组数据:

1000000000 999999999

就是这一个点把我的程序 T 掉了~ 求大神指点数论解法把 \(O(b)\) 优化成 \(O(1)\). ......

Example Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

using namespace std;
typedef long long lli;

int gcd(int x, int y)
{
    if (x == 0)
        return y;
    return gcd(y % x, x);
}

int a, b;

int main(int argc, char** argv)
{
    scanf("%d%d", &a, &b);
    int c = gcd(a, b);
    printf("%d\n", gcd(a, b));
    a /= c, b /= c;
    // Calculating best count used
    if (a == b) {
        printf("0 1\n");
        return 0;
    } else if (a % b == 0) {
        printf("0 1\n");
        return 0;
    }
    int md = a % b;
    int resa = 0, resb = 0;
    int a_div_b = a / b;
    int tmp_md = 0; // (md * i) mod b
    for (int i = 1; i <= b; i++) {
        tmp_md = tmp_md + md; if (tmp_md >= b) tmp_md -= b;
        int tmp_test = b - tmp_md;
        if (tmp_test <= md) resb += a_div_b + 1;
        else resb += a_div_b;
        resa++; // Always guranteed is 1
        if (tmp_test == 1)
            break;
    }
    printf("%d %d\n", resa, resb);
    return 0;
}