Example problem: arc122_e - Increasing LCMs

I did indeed use something like this before, can't remember the exact problem

Wait this algo also gives the smallest set with the given properties?

Great blog! I believe I have used this idea before on trying to implement a way to represent a limited kind of irrational numbers. More precisely, I wanted to represent irrational numbers in the following form.

For convenience, we would also want all values under the root to be square-free, as square factors will be better represented on their multiplied values ("coefficients") instead.

For these values to be square-free, all factors should be below 2, and we can now think of their implicit prime power vector as a binary vector. For convenience, let us define these functions to convert between numbers and their prime power vectors.

Now, we know that multiplying two values gives the sum of the two vectors in its prime power vector. However, we want to keep the powers of each factor to under 2. This lets us think about operations on the F2 field ("binary operations"). We want to keep factors with power of 0 or 1, but remove powers of 2 and move them to the coefficients. We can now define multiplication between two square roots with coefficients in a new way.

Now this lets us compute multiplication of sum-of-roots in quadratic time complexity, assuming there are limited amounts of factors so their implicit vectors can be represented on indexes of arrays (or keys of a map, if you want). The two other operations, addition and subtraction, are very trivial to implement, and so I only explained how multiplication would work.

I have been thinking of a way to do this with FFT since then, but I could still not find a way for it. Please notice me if anyone finds it.

I have a slight implementation question, in the add_element method:

    void add_element(T val){
        for(int i=0;i<basis.size();i++){
            reduce_pair(val, basis[i]);
            if(basis[i] == 1){
                swap(basis[i], basis.back());
                basis.pop_back();
                continue;
            }
            if(val == 1) return;
            if(gcd(basis[i], val) > 1) solve_inner(i, val);
        }
        if(val > 1) basis.push_back(val);
    }

When basis[i] == 1, you do continue after replacing basis[i] with basis.back(). But this essentially means you are skipping over doing reduce_pair on val and what was originally basis.back().

I think this is OK because if basis[i] == 1, this means the original basis[i] had the new val as a divisor and thus every other element of basis[i] will be coprime with the new value of val. But in this case, why not make this a break instead of a continue? I tried submitting your code with a break in place of this continue and it got AC: 176634276

Can you say a little bit more about the $$$\log \log \max (S)$$$ bound? I see that the expected number of prime divisors of a number up to $$$n$$$ is $$$O(\log \log n)$$$, but why the worst case?

Super nice and well-written blog, thanks!

Just found this lol — this reminds me a lot of finding an orthogonal basis of a given vector space!