问题描述 链接到标题

1250.检查“好数组”

解题思路 链接到标题

首先，要注意到，本题的要求，其实可以转化为数组中所有元素的最大公因数为1；

利用辗转相除法，将nums[0]和nums[1]求得的最大公因数num再与nums[2]求最大公因数作为新的num，如果到最后num == 1，返回true，否则返回false。

代码 链接到标题 

class Solution {
  public:
    bool isGoodArray(vector<int> &nums) {
        std::sort(nums.begin(), nums.end()); // 利用哈希表储存不为1的因子，然后遍历，如果最后哈希表为空，return true
        if (nums[0] == 1)
            return true;
        std::unordered_set<int> factor;
        int root = sqrt(nums[0]);
        for (int i = 2; i <= root; i++) {
            if (nums[0] % i == 0) {
                if (factor.empty()) {
                    factor.insert(i);
                    factor.insert(nums[0] / i);
                } else {
                    int flag = 0; // 为0说明factor里面没有它的因子
                    for (auto &num : factor) {
                        if (i % num == 0) {
                            flag = 1;
                            break;
                        }
                    }
                    if (flag == 0) {
                        factor.insert(i);
                        factor.insert(nums[0] / i);
                    }
                }
            }
        }
        if (factor.empty()) {
            factor.insert(nums[0]);
        }
        for (int i = 1; i < nums.size(); i++) {
            auto tmp = factor;
            for (auto &num : tmp) {
                if (nums[i] % num != 0) { // 不是公因子，就移除
                    factor.erase(num);
                }
            }
        }
        return factor.empty();
    }
};

#include <vector>
using std::vector;
class Solution {
  public:
    int gcd(int a, int b) {
        // 其中b^=a,a^=b,b^=a相当于swap(a,b)
        while (b ^= (a ^= (b ^= (a %= b))))
            ;
        return a;
    }
    bool isGoodArray(vector<int> &nums) {
        if (nums.size() == 1)
            return nums[0] == 1;
        for (int i = 0; i < nums.size() - 1; i++) {
            int tmp = gcd(nums[i], nums[i + 1]);
            if (tmp == 1) // 最大公因数已经是1了
                return true;
            nums[i + 1] = tmp;
        }
        return true;
    }
};