主要思路是辗转相除法

1
2
3
4
int gcd(int a, int b)
{
    return b != 0 ? gcd(b, a % b) : a;
}

一个常考性质
一个数可以整除所有数 y1 y2 ..% x
等价这个数 可以整除所有数的最大公约数 y1 y2 …(的公约数) % x