Count Quadruplets

Prerequisite: Prime Factorization(Number Theory)/ Dynamic Programming

Explanation: First let us understand some basic things about LCM $-$

We know LCM of ($2^3\times 3^2$ and $2^2\times 3^3$) is $2^3\times 3^3$.

Here to calculate LCM, we look for the highest power of $2$ and the highest power of $3$ between the numbers. Now if we want to find LCM of ($2^3\times 3^3$ and $2^3\times 3^3$) then LCM will be still $2^3\times 3^3$. So the highest power should be present in at least one of the number.

Let, The LCM of $(a, b, c, d)$ is, $L = 14161$. Now find the total number of quadruplets having LCM equals to $L$.

Prime factorization of $14161 = 17^2\times 7^2$.

So, powers of $17$ till the maximum power available $(17^0, 17^1, 17^2)$ and powers of $7$ till the maximum power available $(7^0, 7^1, 7^2)$ will be distributed in the prime factorization of numbers $a, b, c, d$ such that at least one of $a, b, c, d$ has the highest power of $17$ and at least one of them has the highest power of $7$.

Each of $a, b, c, d$ can have any one of the three powers of $17$ in $3$ ways. So $a, b, c, d$ can have powers of $17$ in $(3\times 3\times 3\times 3) = (2 + 1 )^4 = 81$ ways. But this will also contain cases when $a, b, c, d$ will not have highest power of $17$ so we have to remove those cases.

Cases where highest power is not present in one of $a, b, c, d$ is in $2$ ways. For each of $a, b, c, d$ cannot have highest power of $17$ in $(2\times 2\times 2\times 2) = (1+1)^4 = 16$ ways.

At least one of them has highest power = Total Cases - Cases when none of them has highest power.

$a, b, c, d$ can have powers of $17$, such that at least one of them has the highest power of $17$, in$(2 + 1 )^4 - (1+1)^4 = 81 - 16 = 65$ ways.

Similarly, $a, b, c, d$ can have powers of $7$, such that at least one of them has the highest power of $7$, in $65$ ways.

So total ways $= 65\times 65 = 4225$

See the pattern? So, lets formulate it $-$

Let, $LCM = P_1^{a_1}\cdot P_2^{a_2} … P_n^{a_n}$

So, the number of quadruplets $= [(a_1+1)^4 - a_1^4] \times [(a_2+1)^4 - a_2^4] \times … \times [(a_n + 1)^4 - a_n^4]$

Where, $a_1, a_2, a_3, … ,a_n$ are power of prime factors.

Time Complexity: $O(sqrt(LCM))$

Solution:
Setter’s Solution
Alter’s Solution ( DP Solution )