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)$