I was reading this article, and saw example 1 (number of coprime pairs in range [1, n]). I tried to solve this problem with similar formula. Here's what I wrote:

$$$\sum_{i=1}^n \sum_{j=1}^n [gcd(a_i, a_j) = 1]$$$

$$$ = \sum_{i=1}^n \sum_{j=1}^n \sum_{d|gcd(a_i, a_j)} \mu{(d)}$$$

$$$ = \sum_{i=1}^n \sum_{j=1}^n \sum_{d=1}^{\infty} [d|a_i][d|a_j]\mu{(d)}$$$

$$$ = \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i]) (\sum_{j=1}^n [d|a_j])$$$

$$$ = \sum_{d=1}^{\infty} \mu{(d)} (\sum_{i=1}^n [d|a_i])^2$$$

We can calculate $$$\mu{(d)}$$$ using linear sieve in $$$O(max(a_i))$$$

and $$$\sum_{i=1}^n [d|a_i]$$$ for each $$$d$$$ in $$$O(n * \sqrt{max(a_i)})$$$

But it turns out that when the input is

2
1 2

mu = {1, -1}

cnt = {2, 1}

Gives output of $$$1 * 2^2 + -1 * 1^2 = 3$$$ which is absolutely wrong.

Can anyone point out my mistake? Thanks.