题目:
思想:
@PT, PT_Zhen同学的解法,接下来是他的解法:
如果没有比一大的公约数,那么一定有相差一的时候。
如果两个数直接能够凑成1的话,那么其他数也能通过加减1获得1.一组数中的重大公约数取决于这组数中两个数之间最小的的那个最大公约数[10000, 3, 4], 10000 + 9999 * (3 - 4) = 1
@ylb, 裴蜀定理:我们先可以考虑选取两个数的情况,若选取的数是 aaa 和 bbb,那么根据题目的要求,我们需要满足 a×x+b×y=1a \times x + b \times y = 1a×x+b×y=1,其中 xxx 和 yyy 是任意整数。
根据裴蜀定理,可以得知,如果 a 和 b 互质,那么上述等式一定有解。实际上,裴蜀定理也可以推广到多个数的情况,即如果 a1,a2,⋯,ai
互质,那么 a1×x1+a2×x2+⋯+ai×xi=1一定有解,其中 x1,x2,⋯,xi 是任意整数。
代码:
1 | class Solution: |
1 | class Solution: |