### ljsh_king's blog

By ljsh_king, history, 6 weeks ago,

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.

• +8

 » 6 weeks ago, # |   +7 The $3$ pairs are $(1, 1), (1, 2), (2, 1)$. It's relatively easy to fix the code in such a way that the order of $i, j$ doesn't matter.
•  » » 6 weeks ago, # ^ |   +3 That make sense. Thanks for pointing that out!