Problem :
Sereja wants to answer q queries. In each query, she is given a number N. She wants to find the number of ordered pairs (x, y) such that x and y are factors of N and x and y are coprime.
Constrainsts :
1 ≤ q ≤ 200000
1 ≤ N ≤ 500000
PROOF THE PROBLEM IS NOT FROM AN ONGOING CONTEST
The contest does have an editorial available, but i am unable to understand how the described equation was obtained.
EDITORIAL
Let's consider that solution to your problem is F(N).
I want to solve a bit simpler problem. Let's N = p^a, where p is a prime number.
Let's consider that x will have p^0 in it's factorisation, so we have (a+1) options to select power of p in factorisation of y.
In other case (there are a such cases), we have only one option — select power p equal 0 in factorisation of y.
It's (a+1)+(a), so F(p^a) = (2*a+1).
You can solve problem separately for every power of p[i] in factorization of N. And the answer for N is a multiplication of F(p[i]^a[i]). (these can be proven by Dirichlet convolution if I'm not mistaken).