LeetCode-365-やかん問題(不定次方程式の整数解)

365. Water and Jug Problem
Description

You are given two jugs with capacities x and y litres. 
There is an infinite amount of water supply available. 
You need to determine whether it is possible to measure exactly z litres using these two jugs.

If z liters of water is measurable, you must have z liters of water contained within **one or both** buckets by the end.

Example

Input: x = 3, y = 5, z = 4
Output: True

Solution
問題は、n個の容器a 1,a 2,...,anが与えられたことに変換される.最後にm単位の水が必要です.すなわち、一次不定方程式a1*x1 + a2*x2 + ... + an*xn = mの整数解を求める.
元の問題では,2つの容器x,yしかなかった.方程式は、X*x1 + Y*y1 = Zに整数解があるかどうかとなります.
Hint

二元一次不定式方程式に整数解があるか否かを判断する:XとYの最小公約数がZで

を除去できるか否か

最小公約数を解く:転がり相除去法または更相減損術.

Code

class Solution {	//         x, y     =>       z
public:
	//             
    // a > b     :
    //        a      b,   b       .
    //       ,    b   (a   b    )    。
	int gcd(int a, int b) {
		return a % b == 0 ? b : gcd(b, a % b);
	}

	//      
	// int gcd(int a, int b) {
	// 	if (a == b) return a;
 //        if (a > b) return gcd(a-b, b);
 //        else return gcd(b-a, a);
	// }

    bool canMeasureWater(int x, int y, int z) {
        if (!z) return true;
        if (x + y < z) return false;
        if (!x) return z % y == 0;
        if (!y) return z % x == 0;
        return x > y ? (z % gcd(x, y) == 0) : (z % gcd(y, x) == 0);
    }
};

前に偶然见た知乎は答えた:10 L瓶の水は1つの7 L瓶と3 L瓶を通じて2本の5 L水に分けて、どんな数学の方法でこのような问题を计算しますか?