UVa 10892

From Algorithmist
Jump to navigation Jump to search

10892 - LCM Cardinality[edit]

Summary[edit]

Given a number N, find how many pairs of numbers with have least common multiple equal to N. Basically, a counting problem.

Explanation[edit]

Consider two numbers a and b, whose prime factorizations are and , respectively. Then their LCM is This is the insight that lets us solve the problem.

So factorize N: . Now say that we have a and b such that LCM(a,b) = N. Then for each i, at least one of and is equal to . This would suggest that there are possibilities for each prime factor, and that if we multiply them all together, we're done. Unfortunately, we run into the issue of overcounting. Thus we need to modify this approach somewhat. We will solve this problem incrementally and recursively.

For a given N, call the smallest prime factor , and say that is the largest power of that divides N. Break the problem into two cases. In case one, we set . This gives us possibilities for the first number, and for the rest, we can simply take the product of for . (Verify that this does not count any pairs more than once.) In the other case, we have . In this case, we just need to solve the same problem, but for . (Similarly, verify that these two cases together do not miss any pairs.) The base case of our recursion is when N = 1, in which case we just return 1.

There is another method for calculating the Answer. When we take the product of ,for all i, this value actually counts each distinct pair twice, except the last pair(N,N), it's counted once(Think why, simulate small cases). so we can simply add 1 to that product, and divide it by 2,to get the actual answer.

Implementations[edit]

There does not need to be actual recursion, because we already know the factorization of .

Input[edit]

1
2
12
24
101101291
0

Output[edit]

1 1
2 2
12 8
24 11
101101291 5