Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Tobby_And_Friends's blog

By Tobby_And_Friends, history, 15 months ago, ,

•
• +3
•

 » 15 months ago, # |   0 Finally I solved it . From seeing your code I can guess that you are constructing all pairs of integers whose LCM is n . But the problem is that there are an exponential number of possibilities . My approach was the following , first notice that p and q are always the divisors of n also you can create equivalence classes for p . If n = p1pow1 * ...pkpowk is the prime factorisation of n , then we partition all the divisors into equivalence classes such that a particular equivalence class contains a subset of prime divisors to their highest power and other prime divisors can have smaller powers . For each of the equivalence class in p we consider how many numbers q can be created such that lcm(p, q) = n . This is the abstract of my approach , Take a look at my CODE