problem with counting coprime pairs in an array

Revision en1, by Polyn0mial, 2022-05-27 08:24:29

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Polyn0mial 2022-05-27 08:24:29 1041 Initial revision (published)