Codeforces B.Remainders Game代码超时问题求助

我正在求解Codeforces上的B.Remainders Game问题，推导得出该问题对应如下方程组：

解题思路 #

• 该问题可通过中国剩余定理解决，但我们无需求解（题目未给出d₁,d₂,…,dₙ）。
• 假设满足方程组的解为x，令y为c₁,c₂,…,cₙ的最小公倍数（LCM）。由于LCM是所有cᵢ的公倍数，x加减任意整数倍的y后仍满足原方程组。
• 我们需要判断x%k的值是否唯一，即所有可能的x（x加上y的整数倍）模k的结果是否相同。
• 要满足这一点，需(x+y)%k = x%k，化简后可得y%k=0，即c₁到cₙ的LCM需被k整除。

当前代码 #

#include <iostream>
#include <vector>

using namespace std;

long long GCD(long long a, long long b) {
    if (b == 0)
        return a;

    return GCD(b, a % b);
}

long long LCM(long long a, long long b) {
    return (a * b) / GCD(a, b);
}

int main() {
    int n, k;
    cin >> n >> k;

    long long lcm = 1;
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;

        if (c == k) {
            cout << "Yes";
            return 0;
        }

        lcm = LCM(lcm, c) % k;
        if (lcm == 0) {
            cout << "Yes";
            return 0;
        }
    }

    cout << "No";
}

遇到的问题 #

提交后在测试用例32出现超时（TLE），该测试用例输入大致为：

968661 797449
613021 893 286753 19 198829 515261 913729 707359 47 47 47 372289 19 19 47 47 47 172307 243883 473713 893 47 47 19 281327 150541 47 893 19 799759 19 299209 19 47 683521 893 19 264631 893 311341 169007 47 47 47 19 50923 893 893 893 47 19 706417 880631 945311 19 47 19 47 893 47 47 998819 47 750671 19 19 213319 47 732827 484457 47 893 19 361481 19 26759 47 419537 893 19 47 353299 225779 893 47 831881 129581 893 47 19 19 867463 19 47 893 19 893 893 801503 19 817711 893 893 708619 893 47 47 189853...

当前代码时间复杂度为O(N * log(min(a,b)))，我不清楚该如何优化，请求帮助。

内容的提问来源于stack exchange，提问作者Szyszka947