_dp95's blog

By _dp95, history, 4 weeks ago, In English,

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


The contest does have an editorial available, but i am unable to understand how the described equation was obtained.

  • Vote: I like it
  • +12
  • Vote: I do not like it

4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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).