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

Правка en4, от _dp95, 2019-10-17 00:52:12

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
Теги co-primes, prime-factorisation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en4 Английский _dp95 2019-10-17 00:52:12 0 (published)
en3 Английский _dp95 2019-10-17 00:51:52 12
en2 Английский _dp95 2019-10-17 00:49:54 6 Tiny change: 'e primes, then the n' -> 'e primes, \n\nthen the n'
en1 Английский _dp95 2019-10-17 00:49:15 856 Initial revision (saved to drafts)