有一个由电容组成的计算器，每个电容组件都有最大容量值(正整数)。 对于单个电容器，操作说明如下： 指令1:放电操作-清除电容器当前电量值 指令2:充电操作-将当前电容补充到最大容量值 两个电容A和B，有如下操作指令： 指令3:转移操作-从A中尽可能多地转移电量B，转移不会有电量损失。如果能充满B的最大容量，剩余电量仍将留在A中
现在已知有两个电容，最大容量是a和b其初始状态为0，希望通过一系列操作，使其中一个电容器无论哪一个)中的电量值等于0c（c也是正整数)，这一系列操作中使用的正整数)M，无论如何操作，都不可能完成，此时定义M=0。 显然，每组都确定了a、b、c，会有一个M对应。
输入描述： 每组试样的输入格式为： 第一行是正整数N 从第二行开始，每行由三个正整数组成a、b、c，一共有N组 输出描述： 输出为N行，每行打印每组对应M 备注： 数据范围：
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%） 输入 2 3 4 2 2 3 4 4 0 至少需要4个指令才能完成(3、4、2)： (最大容量为3的是A号电容，另一个是B号电容) 1. 充电A 2. 转移A->B 3. 充电A 4. 转移A->B 此时A中当前电量为2，操作完成，因此输出4。 显然不可能完成(2、3、4)，输出0。
import java.util.Scanner; /** * 请参考参考网站进行分析： * https://blog.csdn.net/u014251675/article/details/81572135 * * @author Liu * @date 2018-08-16 11:51 */ public class DiaoRongChongDian {
public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); long[] A = new long[N]; long[] B = new long[N]; long[] C = new long[N]; // 输入数据 for (int i = 0; i < N; i ) { A[i] = sc.nextLong(); B[i] = sc.nextLong(); C[i] = sc.nextLong(); } // 开始处理数据 for (int i = 0; i < N; i ){ long a = A[i]; long b = B[i]; long c = C[i]; long[] d = ex_gcd(a, b); // 如果c 大于 a和b 亦或是c%d不是0意味着不可能实现 if (c>a&&c>b||c%d[0]!=0){ System.out.println(0); continue; }else if (a==c||b==c){
//c 恰好是b或a，一次就够了 System.out.println(1); continue; }else { long x = d[1]; long y = d[2]; if (d[2]>0){ long temp2 =x;
x = y;
y = temp2;
long temp = a;
a = b;
b = temp;
}
// 使ax + by = c （d是c的因子，即对上面式子ax + by = d两边同时乘以c / d）
long a2 = a/d[0];
long b2 = b/d[0];
x *= c/d[0];
y *= c/d[0];
/* 最小化|x|+|y| * ax+by=c的全部整数解为： * x+kb/gcd(a,b) * y−ka/gcd(a,b), k=...,−2,−1,0,1,2,... * */
long k = x/b2;
x -= k*b2;// 使这组(x, y)最接近0（x > 0时的整数解）
y += k*a2;
long res ;
if (c>a){
res = 2*(x-y);
}else {
res = 2*(x-y-1);
}
x -= b2;// 使这组(x, y)最接近0（y > 0时的整数解）
y += a2;
if (c>b){
res = Math.min(res,2*(y-x)); // 上文分析中假设x > 0，这里y > 0
}else {
res = Math.min(res,2*(y-x-1));
}
System.out.println(res);
}
}
sc.close();
}
/** * 扩展欧里几何 * 存在整数对 x，y ，使得 gcd（a，b）=ax+by * * @param a * @param b * @return 第一个值是最大公约数，第二个值表示C++语言实现中的x，第三个值表示y。 */
public static long[] ex_gcd(long a, long b) {
long ans;
long[] result = new long[3];
if (b == 0) {
result[0] = a;
result[1] = 1;//x
result[2] = 0;//y
return result;
}
long[] temp = ex_gcd(b, a % b);
ans = temp[0];//ans 相当于t
result[0] = ans;
result[1] = temp[2];
result[2] = temp[1] - (a / b) * temp[2];
return result;
}
//普通的最大公约数的求法
public static long common_gcd(long a, long b) {
return a % b == 0 ? b : common_gcd(b, a % b);
}
}
引用https://blog.csdn.net/u014251675/article/details/81572135块内容