I found the problem interesting. Can anyone share the idea behind this problem? I have attached the problem link with this post but may be you need to sign up to see the problem. So I have also attached the Google Drive link of this problem
main source: https://algo.codemarshal.org/contests/icpc-dhaka-19-preli/problems/G
Drive link: Problem number: G (Pairs forming GCD ) https://drive.google.com/open?id=10k4fXa1SZWQM79XbwONUMyAWk70zwMCt
HINT : Learn Euler's totient function
Binary search
Counting pairs $$$x, y$$$ with $$$1\leq x\leq y \leq n$$$ and $$$\gcd(x, y) = g$$$ is equivalent to counting pairs with $$$\gcd(x, y) = 1$$$ in some smaller range
Euler totient function
Precompute
Ignore.