LCMXE - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

Fast prime factorization (sieve of Eratosthenes), simple number theory

PROBLEM:

Given a value Z, count the number of pairs (X, Y) such that 1 \le X, Y \le Z and \text{LCM}(X, Y) \gt Z.

In this version, the sum of Z across all tests is \le 10^6.

EXPLANATION:

There are Z^2 pairs of (X, Y) that satisfy 1 \le X, Y \le Z.
Of them, we’re interested in the ones for which \text{LCM}(X, Y) \gt Z.
Instead of finding this directly, we’ll count the number of pairs for which \text{LCM}(X, Y) \le Z and subtract this from the total.

Note that X, Y \le\text{LCM}(X, Y), i.e. ensuring that the LCM is \le Z automatically ensures that the values are \le Z as well.

So, if we define f(N) to be the number of pairs of integers such that their LCM equals N, we simply need to compute

f(1) + f(2) + \ldots + f(Z)

and we’re automatically guaranteed that all pairs counted will have both values be \le Z.

Now, let’s look at computing f(N) for a fixed value of N.

To do this, we’ll use the prime factorization of N.
Suppose we have

N = p_1^{a_1}p_2^{a_2} \ldots p_k^{a_k}

where p_1, \ldots, p_k are all the distinct prime factors of N, so that a_i \ge 1 for all i.

If we want \text{LCM}(X, Y) = N, then X and Y can also only have some of p_1, \ldots, p_k as their prime factors.
So, let’s write

X = p_1^{b_1}p_2^{b_2} \ldots p_k^{b_k}
Y = p_1^{c_1}p_2^{c_2} \ldots p_k^{c_k}

where b_i, c_i are allowed to be 0 (since it’s ok if a prime factor is missing in one of X or Y as long as the other one covers for it.)

Under this setup, observe that \text{LCM}(X, Y) = N if and only if \max(b_i, c_i) = a_i for every 1 \le i \le k.
That is, for each prime factor of N, the highest power dividing N must be the highest power dividing at least one of X and Y.

Using this, it’s quite easy to count the number of valid pairs (X, Y).

Let’s look at the prime factor p_i.
We want 0 \le b_i, c_i and \max(b_i, c_i) = a_i.
There are exactly 2\cdot a_i + 1 ways to choose such values of b_i and c_i, because:

  • b_i, c_i must both be \le a_i.
  • If 0 \le b_i \lt a_i, then c_i = a_i is forced.
    There are a_i such possibilities here, one for each value of b_i.
  • Similarly, if 0 \le c_i \lt a_i, then b_i = a_i is forced.
    Again, there are a_i possibilities here.
  • Finally, it’s also possible that b_i = c_i = a_i, for one extra possibility.

So, for the prime power p_i, there are 2\cdot a_i + 1 possibilities.
The choices made for each prime are completely independent.
Thus, the total number of choices is obtained by just multiplying the counts for each prime, hence giving us

\prod_{i=1}^k \left(2\cdot a_i + 1\right)

pairs in total.

If the prime factorization of N is known, computing f(N) hence becomes trivial.

The last step remaining is actually computing the prime factorization of N quickly.

One way to do this fast is as follows.

  • Let \text{spf}[n] denote the smallest prime factor dividing n.
    This can be found for all 1 \le n \le Z in \mathcal{O}(Z \log Z) time using the sieve of Eratosthenes.
  • Then, to factorize N, simply let p = \text{spf}[N] and repeatedly divide N by p as long as possible to get its multiplicity; then repeat with the reduced value of N and so on till you reach 1.
    This takes \mathcal{O}(\log N) time because N is divided by (at least) 2 in every step.

TIME COMPLEXITY:

\mathcal{O}(Z\log Z) per testcase.

CODE:

Editorialist's code (PyPy3) 
maxn = 10**6 + 10
spf = [0]*maxn
for i in reversed(range(2, maxn)):
    for j in range(i, maxn, i):
        spf[j] = i

import sys
input = sys.stdin.readline
for _ in range(int(input())):
    z = int(input())
    ans = z*z - 1
    
    for i in range(2, z+1):
        ways = 1
        x = i
        while x > 1:
            p = spf[x]
            ct = 0
            while x%p == 0:
                x //= p
                ct += 1
            ways *= 2*ct + 1
        ans -= ways
    print(ans)