The above problem was encountered in programming competition. I don't know how to solve it. I tried to think using sieve but it won't consider all pair and brute forcing all pairs is not optimal.
Can anyone give idea of the solution?
Consider $\;N\leq 10^5.$
On
I got the approach after hint of karakfa. I think it will work like this. We will first find the numbers which are coprime to n for all $n<=N$ which is $\phi(n)$. To get all pairs $(a,b)$ where $1<=a,b<=N$ whose gcd is x, we can multiply all the pair whose $gcd$ is 1 to x which results in gcd x keeping in mind that it doesn't exeeds $N$ which is managable.
In short, If $(m,n)$ are co-prime, $gcd(x*m,x*n)=x$
As a comment by @karakfa suggests, we need to count the number of relatively prime pairs in $a,b\leq N/x$.
From my answer to this question in MO; Probability that two numbers are relatively prime
It may be useful to have a list of $\{\mu(n): 1\leq n\leq N\}$ where $\mu(n)$ is the Mobius function. Then we can use $$ \sum_{a,b\leq N/x, \ (a,b)=1} 1 = \sum_{a,b\leq N/x}\sum_{d|a,d|b} \mu(d)=\sum_{d\leq N/x} \mu(d)\sum_{a,b\leq N/(xd)}1=\sum_{d\leq N/x} \mu(d)\left\lfloor \frac N{xd}\right\rfloor^2. $$