UVA 10892 - LCM Cardinality

http://uva.onlinejudge.org/external/108/10892.html

You are given a integer \(N\). Your task is to return the number of different integer pairs with lcm equal to \(N\).

A good start is to first think how to get \(N\) as the \(lcm(a,b)\). In order to do that we first need to identify the different values that \(a\) and \(b\) can take. 

After get your hands dirty with couple of sample cases is not hard to see that \(a\) and \(b\) should be taken from the set of divisors of \(N\). The reason behind this is that the \(lcm(a,b)\) takes the maximum exponent from each prime factor of \(a\) and \(b\). The divisors of a number serves as a building block of the number that they divide. In other words contains fragments of the prime factorization of the given number \(N\). Tried another number that is not a divisor of \(N\) is not going to lead us to the correct result.

Let's clarify this thoughts with an example, the pairs that works for \(N = 12\) are the following:

1. \(lcm(1, 12) = 12\)
2. \(lcm(2, 12) = 12\)
3. \(lcm(3, 12) = 12\)
4. \(lcm(4, 12) = 12\)
5. \(lcm(6, 12) = 12\)
6. \(lcm(12, 12) = 12\)
7. \(lcm(3, 4) = 12\)
8. \(lcm(4,6) = 12\)

All this numbers belongs to the set of divisors of 12 that are the following: \(\{1, 2, 3, 4, 6, 12\}\). Note, that in total there are 21 pairs \(( \frac{6 \cdot 5}{2} + 6 \)  but not for all of them we get 12 as lcm. For example \(lcm(3, 6)\) is not 12.

The solution to this problem is to first calculate all the divisors of a given number \(N\) and stored them in the data structure of your preference. For each different pair of divisors we count the ones that \(lcm(d1, d2) = N\).