Tobby_And_Friends's blog

[Number Theory Problem] How do I further optimize my solution for UVa 12546 LCM Pair Sum?
By Tobby_And_Friends, history, 9 years ago, In English

Problem Link: https://uva.onlinejudge.org/external/125/12546.pdf

Solution Link: https://ideone.com/q2SX1x

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

»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply