c++algorithmperformancechinese-remainder-theorem

B. Remainders Game - Codeforces - Time Limit Exceeded


I'm trying to solve this problem: B. Remainders Game

I figured out that this problem give us system of equations as below: enter image description here

And it can be solved using Chinese remainder theorem. But we don't need to solve it (and we haven't given d_1, d_2, ..., d_n)

Let's say we have the result x. The LCM(c_1, c_2, c_3 ... c_n) is y. When we have the LCM of these mods, we can substract and add the y to x infinitely, and the sum (or difference) will also be valid for given equation, because LCM represents every number c_1, c_2, ..., c_n.

So at the end we need to know whether we can unambiguously say the value of x % k. So we need to check whether all possibilities of sum of x and y (let's assume x is the lowest, greater than 0 possible value that satisfy equation) give the same remainder when dividing by k

We can say that (x + y) % k = x % k must be satisfied if we want unambiguous value of x % k

This equation can be simplified to:

x + y = x (mod k), we substract x from both sides, then

y = 0 (mod k)

y % k = 0

So to determine whether the unambiguous solution for x % k exists, we need to check whether LCM(c_1, c_2, c_3, ..., c_n) is divisible by k.

That's my code:

#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";
}

Unfortunelly, I get TLE on test case 32 at Codeforces. I can't see whole input, but its like:

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...

What can I improve in this solution? It's O(N * log(min(a,b))), for a, b used in GCD, I don't see any better way :/


Solution

  • I added these two lines in the beginning of main:

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    

    and it passes all test cases. So the problem was with reading big input.