gcd

365. Water and Jug Problem

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.

Operations allowed:

Fill any of the jugs completely with water. Empty any of the jugs. Pour water from one jug into another till the other jug is completely full or the first jug itself is empty. Example 1: (From the famous "Die Hard" example)

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

Input: x = 2, y = 6, z = 5 Output: False

class Solution {
public:
    bool canMeasureWater(int x, int y, int z) {
        return z == 0 || ((z <= x + y)&&z % gcd(x, y) == 0);
    }
private:
    int gcd(int a, int b){
        return b?gcd(b, a%b):a;
    }
};

辗转相除法

求最大公约数

给定平面上的两个格点P1=(x1, y1)和p2=(x2,y2)，线段p1p2上，除p1和p2以外一共有几个格点?
输入
p1=(1, 11) p2 = (5, 3)
输出
(2, 9)(3, 7)(4, 5)三个点

解法：检查所有满足min(x1,x2)<= x <= max(x1,x2)且min(y1, y2)<=y<=max(y1, y2)的格点。

其实这道题的答案是|x1 - x2|和|y1 - y2|的最大公约数-1(但|x1-x2| = 0且|y1 - y2| = 0时的答案是0)。 求最大公约数

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

拓展欧几里得算法(Euclidean algorithm)

双六

一个双六上面有向前向后无限延续的格子，每个格子都写有整数。其中0号格子是起点，1号格子是终点。而骰子上只有a,b,-a,-b四个整数，所以根据a和b的值得不同，有可能无法到达终点。
....|-4|-3|-2|-1|0|1|2|3|4|....
掷出四个整数个多少次可以到达终点了？如果解不唯一，输出任何一组皆可。如果无解，输出-1.
输入
a = 4, b =11
输出
3001(3 *a - 1*b)

上述问题用数学语言表示就是求得x,y使得ax + by = 1。我们发现，如果gcd(a, b) != 1,显然无解。反之，就可以通过扩展原来的辗转相除法来求解。

扩展欧几里德算法

基本算法：对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。

证明：设 a>b。

  1，显然当 b=0，gcd（a，b）=a。此时 x=1，y=0；

  2，ab!=0 时

  设 ax1+by1=gcd(a,b);

  bx2+(a mod b)y2=gcd(b,a mod b);

  根据朴素的欧几里德原理有 gcd(a,b)=gcd(b,a mod b);

  则:ax1+by1=bx2+(a mod b)y2;

  即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;

  根据恒等定理得：x1=y2; y1=x2-(a/b)*y2;

     这样我们就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.

   上面的思想是以递归定义的，因为 gcd 不断的递归求解一定会有个时候 b=0，所以递归可以结束。

int extgcd(int a, int b, int &x, int &y){
  int d = a;
  if(b != 0){
    d = extgcd(b, a%b, y, x);
    y -= (a/b)*x;

    /*上面的式子等价于下面的结果，由底层往上层迭代。
     d = extgcd(b, a%b, x, y);
     int t = x;
     x = y;
     y = t - a/b*y;
     */
  }else{
    x = 1; y = 0;
  }
  return d;
}