On the most recent Bleddest Div 2, I used gcd instead of mod, thinking I wouldn't get punished.

Becuase O(n^2 log 10^9) = 30 * 5000 * 5000 = 7.5 * 10^8 which should pass.

But it turns out that the C++ built in gcd uses the Euclidian Algorithm:

int gcd (int a, int b) {
    return b ? gcd (b, a % b) : a;
}

Hacked Submission: https://codeforces.me/contest/2283/submission/397357386

So the next time you want to compute GCD, use Stein’s algorithm:

int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

I get the easy AC after getting hacked :( https://codeforces.me/contest/2283/submission/397490186

So what do you guys think about the built in gcd?