AtCoder ABC 230 G GCD Permutation

This is my understanding of ABC 230 G GCD Permutation problem.
The original problem can be available here.
The official solution is available here.

Mobius Function

The Mobius function is defined as follows:
$ \mu(n) = 1 $: $n$ is a square-free integer with even number of prime factors. (Including $0$)
$ \mu(n) = -1 $: $n$ is a square-free integer with odd number of prime factors.
$ \mu(n) = 0 $: Otherwise. $n$ has a squared prime factors.
Take a look at examples.
$~~~~~ n=1$: Since $1$ is not a prime, $\mu(n)=1$.
$~~~~~ n=2$: $\mu(n)=-1$.
$~~~~~ n=3$: $\mu(n)=-1$.
$~~~~~ n=4$: Since $4=2^2$, $\mu(n)=0$.
$~~~~~ n=5$: $\mu(n)=-1$.
$~~~~~ n=6$: Since $6=2 \cdot 3$, $\mu(n)=1$.
$~~~~~ n=7$: $\mu(n)=-1$.
$~~~~~ n=8$: Since $8=2^3$, $\mu(n)=0$.
$~~~~~ n=9$: Since $9=3^2$, $\mu(n)=0$.
$~~~~~ n=10$: Since $10=2 \cdot 5$, $\mu(n)=1$.

Using this function, you obtain
$~~~~~ \sum_{d|n} \mu(d) = \left\{ \begin{array}{ll} 1 & (n=1) \\ 0 & (n \geq 2) \end{array} \right. $
where $d|n$ indicates that for all divisors of n.
For example,
$~~~~~ n=1$, $d=\{1\}$, therefore, $\sum_{d|n} \mu(d) = 1$.
$~~~~~ n=2$, $d=\{1,2\}$, therefore, $\sum_{d|n} \mu(d) = 1 + (-1) = 0$.
$~~~~~ n=4$, $d=\{1,2,4\}$, therefore, $\sum_{d|n} \mu(d) = 1 + (-1) + 0 = 0$.
$~~~~~ n=6$, $d=\{1,2,3,6\}$, therefore, $\sum_{d|n} \mu(d) = 1 + (-1) + (-1) + 1 = 0$.

Mobius Function (modified)

For this problem, we need a slightly different function from the original mobius function that produces
$~~~~~ \sum_{d|n} \tilde{\mu}(d) = \left\{ \begin{array}{ll} 0 & (n=1) \\ 1 & (n \geq 2) \end{array} \right. $
To get this function, we need to define a modified Mobius function as
$\tilde{\mu}(n) = 1$ if $n$ is a square-free integer with odd number of prime factors.
$\tilde{\mu}(n) = -1$ if $n$ is a square-free integer with even number of prime factors. (Not including $0$)
$\tilde{\mu}(n) = 0$ Otherwise. $n$ has a squared prime factors.

Brute Force

Let’s start with a brute force approach. We define $GCD(i,j)=g$ and $GCD(p_i,p_j)=g’$. To solve this problem, we need to count the number of cases where $g \geq 2$ and $g’ \geq 2$ for all $1 \leq i \leq j \leq N$. This can be described as follows using the modified Mobius function above,
$~~~~~ S = \sum_{1 \leq i \leq j \leq N} \sum_{a|g} \sum_{b|g’} \tilde{\mu}(a) \tilde{\mu}(b)$
This is because $\sum_{a|g} \sum_{b|g’} \tilde{\mu}(a) \tilde{\mu}(b) = 1$ only if $g \geq 2$ and $g’ \geq 2$, and otherwise, $\sum_{a|g} \sum_{b|g’} \tilde{\mu}(a) \tilde{\mu}(b) = 0$. We formulate the modified Mobius function to get this property.
This equation can also be transformed to not holding greatest common devisor culculation by using $f(i,j;a,b)$.
$~~~~~ S = \sum_{1 \leq i \leq j \leq N} \sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b) f(i,j;a,b)$
where $f(i,j;a,b)=1$ if $i$ is a multiple of $a$, $p_i$ is a multiple of $b$, $j$ is a multiple of $a$, and $p_j$ is a multiple of $b$, and $f(i,j;a,b)=0$ otherwise.
Now, $S$ can be easier to code but it requires $O(N^4)$ running time. We need one more trick to compute this in a given time limit.

Speed UP

So far, we got
$~~~~~ S = \sum_{1 \leq i \leq j \leq N} \sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b) f(i,j;a,b)$
Here, we introduce another function $num(a,b)$, which is a number of integer $k$ such that $1 \leq k \leq N$, $k$ is a multiple of $a$, and $p_k$ is a multiple of $b$. Then, we have
$~~~~~ \sum_{1 \leq i \leq j \leq N} f(i,j;a,b) = \frac{num(a,b)(num(a,b)+1)}{2}$
This is because for a given pair of $(a,b)$, we have $num(a,b)$ choices for $i$ and $j$. When $i \neq j$, we have $\frac{num(a,b)(num(a,b)-1)}{2}$ combinations because of $i<j$ while if $i=j$, we have $num(a,b)$ choices for $i$ and $j$. Summing up these two yields $\frac{num(a,b)(num(a,b)-1)}{2} + n = \frac{num(a,b)(num(a,b)+1)}{2}$.
Now, $S$ can be calculated as
$~~~~~ S = \sum_{a=1}^N \sum_{b=1}^N \tilde{\mu}(a) \tilde{\mu}(b) \frac{num(a,b)(num(a,b)+1)}{2}$

Running Time Analysis

The final formula looks $O(N^2)$ since we need to loop over from $1$ to $N$ for both $a$ and $b$. However, $\tilde{\mu}= 0$ for many $a$ and $b$, and we need to focus only on a pair of $a$ and $b$ that $\tilde{\mu} \neq 0$.

1.$~$ For $a$ from $1$ to $N$
2.$~~~~$ If $\tilde{\mu}(a) \neq 0$
3.$~~~~~~~$ For each $i$ that is a multiple of $a$ and is smaller than $N$
4.$~~~~~~~~~~$ For eash divisor $b$ of $p_i$ such that $\tilde{\mu}(b) \neq 0$
5.$~~~~~~~~~~~~~$ $num(a,b) = num(a,b) + 1$

In the rough pseudocode above, we focus only on $a$ such that $\tilde{\mu}(a) \neq 0$ in line 2, and calculate $num(a,b)$ in line 3 to 5. The for-loop in line 1 takes $O(N)$ and the for-loop in line 3 requires $O(\frac{N}{a})$. About the for-loop in line 4, we have at most 63 divisors because $2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17=510510>200000$ and $2^6-1=63$. Therefore, the entire run time will be $\sum_{a=1}^N \frac{N}{a} \cdot 63 \approx 63 N \log N \approx 2 \cdot 10^8$.

Why Mobius Function?

This problem can be solved by using the modified version of the Mobius function. As we saw in the run time analysis part, the Mobius function returns $0$ for numbers that have squared prime factors, and in fact, for a given $N$, only a small portion of integers less than $N$ has the Mobius function not equal to $0$. This results in greatly reducing the computational cost and this is the major advantage of using the Mobius function.
The implementation of this problem is not that difficult because it doesn’t require to use advanced algorithms and data structures. I would say this is much of a math problem.