Polyn0mial's blog

By Polyn0mial, history, 2 years ago, In English

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.

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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.