# UVa 10892

## Summary

Given a number N, find how many pairs of numbers ${\displaystyle (a,b)}$ with ${\displaystyle a\leq b}$ have least common multiple equal to N. Basically, a counting problem.

## Explanation

Consider two numbers a and b, whose prime factorizations are ${\displaystyle 2^{a_{2}}3^{a_{3}}...}$ and ${\displaystyle 2^{b_{2}}3^{b_{3}}...}$, respectively. Then their LCM is ${\displaystyle 2^{max(a_{2},b_{2})}3^{max(a_{3},b_{3})}...}$ This is the insight that lets us solve the problem.

So factorize N: ${\displaystyle p_{1}^{n_{1}}p_{2}^{n_{2}}...p_{k}^{n_{k}}}$. Now say that we have a and b such that LCM(a,b) = N. Then for each i, at least one of ${\displaystyle a_{i}}$ and ${\displaystyle b_{i}}$ is equal to ${\displaystyle n_{i}}$. This would suggest that there are ${\displaystyle 2n_{i}+1}$ 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 ${\displaystyle p_{1}}$, and say that ${\displaystyle n_{1}}$ is the largest power of ${\displaystyle p_{1}}$ that divides N. Break the problem into two cases. In case one, we set ${\displaystyle a_{1}. This gives us ${\displaystyle n_{1}}$ possibilities for the first number, and for the rest, we can simply take the product of ${\displaystyle (2n_{i}+1)}$ for ${\displaystyle i>1}$. (Verify that this does not count any pairs more than once.) In the other case, we have ${\displaystyle a_{1}=b_{1}=n_{1}}$. In this case, we just need to solve the same problem, but for ${\displaystyle {\frac {N}{p_{1}^{n_{1}}}}}$. (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 ${\displaystyle (2n_{i}+1)}$,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

There does not need to be actual recursion, because we already know the factorization of ${\displaystyle {\frac {N}{p_{1}^{n_{1}}}}}$.

## Input

1
2
12
24
101101291
0


## Output

1 1
2 2
12 8
24 11
101101291 5