题目描述

有一台用电容组成的计算器，其中每个电容组件都有一个最大容量值（正整数）。
对于单个电容，有如下操作指令：

• 指令1：放电操作 - 把该电容当前电量值清零；
• 指令2：充电操作 - 把该电容当前电量补充到最大容量值；
• 指令3：转移操作 - 从电容$A$中尽可能多的将电量转移到电容$B$，转移不会有电量损失，
  如果能够充满$B$的最大容量，那剩余的电量仍然会留在$A$中。

$\quad$现在已知有两个电容，其最大容量分别为$a$和$b$，其初始状态都是电量值为$0$，希望通过一系列
的操作可以使其中某个电容（无所谓哪一个）中的电量值等于$c$（$c$也是正整数），这一系列操作
所用的最少指令条数记为$M$，如果无论如何操作，都不可能完成，则定义此时$M=0$。显然对于每一
组确定的$a,b,c$，一定会有一个$M$与之对应。

输入描述：

每组测试样本的输入格式为：
第一行是一个正整数$N$；
从第二行开始，每行都是$3$个正整数依次组成一组$a,b,c$,一共有$N$组；

输出描述：

输出为$N$行，每行打印每一组对应的$M$

样例

输入：

2
3 4 2
2 3 4

输出：

4
0

说明
对于$(3,4,2)$，最少只需要$4$个指令即可完成：
（设最大容量为$3$的是$A$号电容，另一个是$B$号电容）
操作：（充电$A$）=> （转移$A$ -> $B$） => （充电$A$）=> （转移$A$ -> $B$）。

对于$(2,3,4)$，显然不可能完成，输出$0$。

备注：
数据范围：
$N:0<N<100$；

$a,b,c$

$0<a,b,c<10^5(50\%)$
$0<a,b,c<10^7(30\%)$
$0<a,b,c<10^9(20\%)$

算法设计与分析

(扩展欧几里得算法，裴蜀定理)

时间复杂度: $O(NlogV)$

$\quad$此题为LeetCode 365. Water and Jug Problem的扩展版。
$\quad$首先，根据$Y$总的LeetCode 365. 水壶问题（LeetCode究极班）视频讲解，我们可以将两个电容的状态视为一个整体进行考虑。那么可以证明：

引论1：这个整体与外部之间的交互只需要包含$+a$、$-a$、$+b$、$-b$四种操作。

$\quad$简略证明：假设这个整体还需要中间数值的电容量q（即$0<q<a$或$0<q<b$）与外界交互。
那么在充入(或者释放)$q$电量之前，整体的状态只可能是以下两种情况之一：
1. 一个电容为空，另一个电容半满不满；
2. 一个电容为满，另一个电容半满不满
$\quad$我们简单分析一下情况1（情况2的分析类似）。在情况1的状态下，如果是充入电量$q$将整体
状态变为一空一满，那么我们可以从初始状态通过前面讲的四种操作达到同样的状态，
并且操作次数更少。也就是说为了到达目标状态（一空一c或者一满一c），从初始状态开始
变换，整体与外界的交互只需要$+a$、$-a$、$+b$、$-b$四种操作就足够了。

$\quad$在证明完引论1之后，那么问题就转换成了：等式$ax+by=c$是否存在整数解。$x,y$的符号
为正代表充电，为负代表放电。根据裴蜀定理，等式成立当且仅当$gcd(a,b)|c$。

$\quad$我们现在来考虑当$gcd(a,b)|c$时，如何计算最少操作次数：
$\quad$根据裴蜀定理，存在整数$x,y$，使得$ax+by=c$，且由于$c≤Max(a,b)$，所以$x,y$一定一正一负，
或者一正一零。

$\quad$对于一正一零的情况，
1. 如果是$x>0,y=0$（即$a|c$），那么$a \le c \le b$，若此时$a=c$，那么只需充电$1$次；若此时$a<c$，
那么需要的充电次数为$x$次，放电次数为$0$次，转移次数为$x$次，总共操作次数为$2x$次。
2. 对于$x=0,y>0$的情况类似，若此时$b=c$，总共操作次数只需$1$次；否则，总共操作次数为$2y$次。

$\quad$接着，我们继续分析一正一负的情况：
此时$a,b,c$三者之间的关系可能如下(由于前面已经分析过一正一零的情况，这里不需要再考虑$c =b$或者$c=a$的情况)：

1. $a<c$，那么此时应该有$c \lt b$;
2. $c \lt a$，
   2.1. $b < c$;
   2.2. $b \gt c$,此时
   2.2.1. $c<a<b$
   2.2.2. $c<b<a$

$\quad$不妨先假设$x \gt 0$，然后根据上述$a,b,c$的大小关系逐一分析。
$\quad$1. 先分析$a \lt c \lt b$时。此时，由于$x>0$并且$a<b$，那么操作序列就是：

$$+a,转移,+a,转移,\dots,+a,转移,-b,转移,+a,转移,\dots$$

$\quad$由于$a \lt c$，那么最终是$B$里存储着目标电量$c$。根据上述操作序列，一共有$x$次充电操作，$-y$次放电操作，$x-y$次转移操作，总操作次数为$2x-2y$。注意，上述操作序列里$-b$之后的转移操作，此次的转移操作所转移的电量是小于$b$的；在这之前的转移操作都是从A转 移电量到B，并且将B加满，这是为了保证整体与外界之间的操作只包含$+a$、$-a$、$+b$、$-b$这四种操作。注意，由于我们前面已经分析完了一正一零的情况，所以$-b$放电后的转移操作必不可少。
$\quad$2. 然后，我们分析$b \lt c \lt a$（即2.1.）的情况。其操作序列大概如下：

$$+a,转移,-b,转移,-b,转移,\dots,转移,-b,转移,+a,转移,-b,转移,\dots$$

$\quad$此时，电容$A$里首先出现$c$电量（这是由我们前面的假设$x\gt0$所决定的）。上述序列里，
每个$+a$操作后都跟着一个转移操作，每个$-b$操作后跟着一个转移操作。但请注意，根据题意，
当电量$c$出现在电容$A$里时，电容$B$里无需再进行本次的$-b$操作，从而操作序列里跟随在本次$-b$操作
后的转移操作也无从谈起。这样，充电操作进行了$x$次，放电操作进行了$-y-1$次，转移操作进行
了$x-y-1$次，最终整体里的电量状态为电容A里存储着c电量，电容B里存储着b电量，总共的操作次数为$2x-2y-2$次。

$\quad$3. 对于$c<a$且$c<b$的情况分析逻辑是类似的，在此就不再赘述了，直接给出结论：
总共的操作次数为$2x-2y-2$次。

$\quad$在分析完上述一正一零和一正一负的情况后，我们发现，只需要最小化$\vert x \vert + \vert y \vert$的值。可以先用
扩展欧几里得算法求出任意一组$(x,y)$，则

$$\begin{cases} x+kb/gcd(a,b) \\[2ex] y-ka/gcd(a,b) \end{cases} , k = …, -2, -1, 0, 1, 2, …$$

就是该等式的全部整数解，我们找出和$0$最接近的两组$(x,y)$（一组$x>0$, 另一组$y>0$，然后取操作次数
较小的一组即可）

时间复杂度分析：扩展欧几里得算法的复杂度是$O(logV)$，一共 N组测试数据，所以总时间复杂度是$O(NlogV)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

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

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        LL a, b, c, x, y;
        cin >> a >> b >> c;
        int d = gcd(a, b, x, y);
        if (c > a && c > b || c % d)
        {
            cout << 0 << endl;
            continue;
        }
        if (c == a || c == b)
        {
            cout << 1 << endl;
            continue;
        }
        if (y > 0) swap(x, y), swap(a, b);
        LL a2 = a / d, b2 = b / d;
        x *= c / d, y *= c / d;
        LL k = x / b2;
        x -= k * b2, y += k * a2;
        LL res;
        if (c > a) res = 2 * (x - y);
        else res = 2 * (x - y - 1);
        x -= b2, y += a2;
        if (c > b) res = min(res, 2 * (y - x));
        else res = min(res, 2 * (y - x - 1));
        cout << res << endl;
    }
    return 0;
}

参考文献：

1. 今日头条2018暑期实习在线笔试题解-题目5
2. 电容充电-字节跳动2018秋