### _dp95's blog

By _dp95, history, 8 months ago, ,

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

• +12

 » 8 months ago, # |   +3 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).