how to find number of ordered pairs (x, y) such that x and y are factors of N and x and y are coprime??

Revision en1, by _dp95, 2019-10-17 00:49:15

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
Tags co-primes, prime-factorisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English _dp95 2019-10-17 00:52:12 0 (published)
en3 English _dp95 2019-10-17 00:51:52 12
en2 English _dp95 2019-10-17 00:49:54 6 Tiny change: 'e primes, then the n' -> 'e primes, \n\nthen the n'
en1 English _dp95 2019-10-17 00:49:15 856 Initial revision (saved to drafts)