## Sunday, July 01, 2012

### 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$.