[Java/C++/Python] Chinese Remainder Theorem
Intuition\nThis problem is realated a Chinese theorem:\nChinese remainder theorem, created in 5th centry.\nAlso well known as Hanson Counting.\n\n\n## Explanati
## **Intuition**\nThis problem is realated a Chinese theorem:\nChinese remainder theorem, created in 5th centry.\nAlso well known as Hanson Counting.\n<br>\n\n## **Explanation**\nIf `a % x = 0` and `b % x = 0`,\nappareantly we have `(pa + qb) % x == 0`\nIf `x > 1`, making it impossible `pa + qb = 1`.\n\nWell, I never heard of Bezout\'s identity.\nEven though the intuition only proves the necessary condition,\nit\'s totally enough.\n\nThe process of gcd,\nis exactly the process to get the factor.\nThe problem just doesn\'t ask this part.\n<br>\n\n## **Complexity**\nOf course you can return true as soon as `gcd = 1`\nI take gcd calculate as `O(1)`.\n\nTime `O(N)`\uFF0C\nSpace `O(1)`\n\n<br>\n\n**Java:**\n```java\n    public boolean isGoodArray(int[] A) {\n        int x = A[0], y;\n        for (int a: A) {\n            while (a > 0) {\n                y = x % a;\n                x = a;\n                a = y;\n            }\n        }\n        return x == 1;\n    }\n```\n\n**C++:**\n```cpp\n    bool isGoodArray(vector<int>& A) {\n        int res = A[0];\n        for (int a: A)\n            res = gcd(res, a);\n        return res == 1;\n    }\n```\n\n**Python:**\n```python\n    def isGoodArray(self, A):\n        gcd = A[0]\n        for a in A:\n            while a:\n                gcd, a = a, gcd % a\n        return gcd == 1\n```\n\n**Python, 1-line using fractions**\n```python\nimport fractions\nclass Solution(object):\n    def isGoodArray(self, A):\n        return reduce(fractions.gcd, A) < 2\n```
[]