Editorial for Count Quadruplets

Prerequisite: Prime Factorization(Number Theory)/ Dynamic Programming

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

We know LCM of (23×322^3\times 3^2 and 22×332^2\times 3^3) is 23×332^3\times 3^3.

Here to calculate LCM, we look for the highest power of 22 and the highest power of 33 between the numbers. Now if we want to find LCM of (23×332^3\times 3^3 and 23×332^3\times 3^3) then LCM will be still 23×332^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)(a, b, c, d) is, L=14161L = 14161. Now find the total number of quadruplets having LCM equals to LL.

Prime factorization of 14161=172×7214161 = 17^2\times 7^2.

So, powers of 1717 till the maximum power available (170,171,172)(17^0, 17^1, 17^2) and powers of 77 till the maximum power available (70,71,72)(7^0, 7^1, 7^2) will be distributed in the prime factorization of numbers a,b,c,da, b, c, d such that at least one of a,b,c,da, b, c, d has the highest power of 1717 and at least one of them has the highest power of 77.

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

Cases where highest power is not present in one of a,b,c,da, b, c, d is in 22 ways. For each of a,b,c,da, b, c, d cannot have highest power of 1717 in (2×2×2×2)=(1+1)4=16(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,da, b, c, d can have powers of 1717, such that at least one of them has the highest power of 1717, in(2+1)4(1+1)4=8116=65 (2 + 1 )^4 - (1+1)^4 = 81 - 16 = 65 ways.

Similarly, a,b,c,da, b, c, d can have powers of 77, such that at least one of them has the highest power of 77, in 6565 ways.

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

See the pattern? So, lets formulate it -

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

So, the number of quadruplets =[(a1+1)4a14]×[(a2+1)4a24]××[(an+1)4an4]= [(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, a1,a2,a3,,ana_1, a_2, a_3, … ,a_n are power of prime factors.

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

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

    Statistics


    85% Solution Ratio

    YouKnowWhoEarliest, 3M ago

    likhon5Fastest, 0.0s

    YouKnowWhoLightest, 131 kB

    Deshi_TouristShortest, 359B

    Toph uses cookies. By continuing you agree to our Cookie Policy.