Disjoint Set Union is used in this way, making the representative element of each position equal to the first non-zero position after this position. You can check out the Alternative Code $$$O(n\alpha (n))$$$.

ok, fixed.

In fact, there is an $$$O(n)$$$ solution for problem E(submission). I have explained it in in the "Alternative Solution" section.

In fact, there is an $$$O(n)$$$ solution for problem E(submission). I have explained it in in the "Alternative Solution" section.

I didn't get a compile timeout in the custom test, even though it took a long time to compile.

#pragma GCC unroll is faster to compile than C++ templates.

vector<u32> factor(u32 x) {
    vector<u32> vec;
    #pragma GCC unroll 3401
    for (int i = 0; i < 3401; i++)
        if (x % primes[i] == 0) [[unlikely]]
            factor_helper(vec, x, primes[i]);
    if (x > 1)
        vec.push_back(x);
    return vec;
}

Thank you, it has been fixed.

Thank you, it has been fixed.

Can anyone explain the O(n) solution of the F problem (official editorial)? Even though I've gotten AC, I still can't understand the official editorial.

Thanks.

94684 is about twice 47312, I think the reason for this is that you changed inSZ from 1 << 17 to 1 << 18, so I still think it's cin.tie(0)->sync_with_stdio(0) that's causing the fread error.

sync_with_stdio is a static function of class ios, so cin.tie(0)->sync_with_stdio(0) is equivalent to cin.tie(0), ios::sync_with_stdio(0).

The problems will be in Chinese (Simplified). In this contest, we'll put brief English statements in the attachments, but it's still strongly encouraged that you learn Chinese for maximized functionality of our website.

Are you kidding me, can anyone learn Chinese in three days?

When k=1 my method is the same as Lemire Reduction, but there are some differences:

• The purpose of my method is to compute $$$a_i\times k \bmod m$$$ multiple times for fixed $$$m,k$$$, while Lemire Reduction is modulo a single number.
• When computing $$$a_i\times k \bmod m$$$, my method works for $$$m \lt 2^{32}$$$ and with two 64-bit multiplications. If you calculate $$$a_i\times k$$$ first and then use Lemire Reduction, it only works for $$$m \lt \sqrt[3]{2^{64}}$$$ with three 64-bit multiplications.

Maybe my method is an improvement of Lemire Reduction, which works for $$$m \lt 2^{32}$$$ and is useful in competitive programming (common moduli are $$$10^9+7$$$ and $$$998244353$$$)

Thanks for your suggestion. I've changed the external links to spoiler tags and compared my method to the others.

Auto comment: topic has been updated by platelet (previous revision, new revision, compare).

137_345_2814 will win IOI2022!