Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### Mhn_Neek's blog

By Mhn_Neek, history, 5 weeks ago,

How to find the number of pairs of integers (x,y) such that gcd(x,y) = 1?
n<=1e6
x<y<=n
time limit = 2s

• -4

 » 5 weeks ago, # | ← Rev. 2 →   +6 Euler's totient function is the function $\phi(n) =$ the number of numbers $\le n$ and coprime to $n$. Sum that for all $y$ from $2$ to $n$
 » 5 weeks ago, # | ← Rev. 6 →   +2 Hint: DP.Solution: Let us solve the more general problem: how do you find the number of pairs ($p[d]$) of integers $(x, y)$ with a gcd of $d$?Let $cnt[x]$ mean the number of times $x$ occurs as a divisor of a number in $a$. We would calculate this by iterating over all $a_i$ and finding its divisors, incrementing $cnt[d]$ for each divisor (in $O(n \sqrt[3]{n}$)What if $d=\max{a_i}$? Then the answer is $\frac{cnt[d] \cdot (cnt[d]-1)}{2}$. Otherwise, let us initialize the answer for some $x<\max{a_i}$ to $\frac{cnt[x] \cdot (cnt[x]-1)}{2}$. This is almost correct, but will also count pairs with a gcd of $2x$, $3x$, $4x$, and so on. So we will subtract $p[2x]$, $p[3x]$, $p[4x]$. This will take $O(n \log{n})$ time.Here's my code for Counting Coprime Pairs on CSES. Hope this helped!
 » 5 weeks ago, # |   +1 It can be done fast using mobius inversion: https://mirror.codeforces.com/blog/entry/53925