Preparing a lookup table in binary GCD can be somewhat effective if the inputs are small. I've seen a 30% time reduction with a 512x512 table (which consumes almost no memory and time) for inputs less than $$$2\times10^9$$$. It scales quite linearly with the log.

int lut[512][512];
uint32_t faster_binary_gcd(uint32_t u, uint32_t v)
{
    auto zu = std::countr_zero(u);
    auto zv = std::countr_zero(v);
    auto shift = std::min(zu, zv);
    u >>= zu;
    v >>= zv;
    do
    {
        if (u < 512)
            return lut[u][v % u] << shift;
        uint32_t u_minus_v = u - v;
        if (u > v)
        {
            u = v, v = u_minus_v;
        }
        else
        {
            v = v - u;
        }
        v >>= std::countr_zero(u_minus_v);
    } while (v != 0);
    return u << shift;
}

It comes to my mind that while some problems have obviously wrong solutions, they're still accepted in an algorithmic contest. E.g. https://mirror.codeforces.com/blog/entry/147991, or (possibly) https://qoj.ac/contest/1901/problem/8614, https://dmoj.ca/problem/coci16c4p4. Would this be regarded as an error, or actually acceptable? (Output only, or partial scoring problems are excluded from this).

A common "excuse" is to generate weak tests to deliberately make the intended etc. solutions pass.

It seemed that this problem got not much more development going to it since its introduction, so my solution is still the fastest after nearly a year: https://judge.yosupo.jp/submission/268155.

There're only two main optimizations: AVX input, and back-substitution using Method of Four Russians (this is how I became the fastest over adamant's lead.)

Would there be a faster solution to this problem?

I've discovered two more GP modes:

https://mirror.codeforces.com/contests/2147,2164,2180,2179/gp10/best4/standings?mobile=false

https://mirror.codeforces.com/contests/2147,2164,2180,2179/gp30/best4/standings?mobile=false

https://mirror.codeforces.com/contests/2147,2164,2180,2179/gp100/best4/standings?mobile=false

Please respect the function $$$dmax(n)$$$ by actually using it, instead of masquerading it for a random function that serves as a very rough approximation. Context: $$$dmax(n)$$$ is $$$max_{1\leq i \leq n}\tau(n)$$$.

Hey MikeMirzayanov, can you fix the mirror website of codeforces, it's useful for many people. Thanks!
UPDATE: mirror codeforces is back!!