P1250 - Check If It Is a Good Array, Leetcode

Problem Description

给 定nums[i], 求解 $y_i\in \text{Z}$, 使得 ${\sum }_{i=0}^{n-1}{y}_i\times x_i=1$, 其中 $x_i=nums[i]$.

若有解返回true, 否则返回flase.

Analysis

裴蜀定理, 又称贝祖定理(Bézout's lemma), 是一个关于最大公约数的定理. 其内容是:

设 $a$, $b$ 是不全为 $0$ 的整数, 则对于任意的整数 $x$ 和 $y$ , 有且只有 $ax+by=k\gcd (a,b)$ 成立, 其中 $k$ 为整数.

可推广到 $n$ 个整数.

Code

java

class Solution {
    public boolean isGoodArray(int[] nums) {
        int g = 0;
        for (int x : nums) {
            g = gcd(x, g);
        }
        return g == 1;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a;
            a = b;
            b = t % b;
        }
        return a;
    }
}

Complexity Analysis

• Time: $O(n+\log (\text{max}))$
• Space: $O(1)$