DevuAndEqualizingLCM | Topcoder Archive

Problem Statement

Devu has two arrays A and B. All elements of these arrays are positive integers.

Devu wants to have two arrays that have the same LCM (least common multiple) of all their elements.

Devu is only allowed to modify array B. In each step, he can change the value at some index in B to an arbitrary positive integer.

(Note that the new integer can be arbitrarily large, possibly much larger than what is allowed by the input constraints.)

Compute and return the minimum number of steps Devu needs to take.

Definition

Class:: DevuAndEqualizingLCM
Method:: minimumOperationsNeeded
Parameters:: long[], long[]
Returns:: int
Method signature:: int minimumOperationsNeeded(long[] A, long[] B)
(be sure your method is public)

Constraints

A will have between 1 and 50 elements, inclusive.
B will have between 1 and 50 elements, inclusive.
Each element of A and B will be between 1 and 1012, inclusive.

Examples

```
{2, 3}
```
```
{6}
```
```
Returns: 0
```
The least common multiple of each array is 6. As the arrays already have the same LCM, no steps are needed.
```
{2, 6}
```
```
{4, 6}
```
```
Returns: 1
```
LCM(A) is 6 while LCM(B) is 12. You can change B[0] from 4 to 2 in a single step. This will clearly make the LCMs of both arrays equal (as now the arrays themselves are equal).
```
{4, 6, 10}
```
```
{7, 7, 60, 20}
```
```
Returns: 2
```
```
{5, 4, 6}
```
```
{7, 9, 13}
```
```
Returns: 3
```

{41,100,28,55,67,34,20,83,45,8,27,95,1,43,7,88,60,71,16,31,89,75,75,3,60,56,76,38,5}

{91,15,55,42,46,81,45,27,66,26,83,48,90,100,34,32,31,27}

Returns: 5

{97540245831,137068896362,514711863869,493787121165,834951815745,37979891065,568618248989,845422774812,388880393645,
985781954575,604319452958,746201820162,231152838059,216843527666,273129662502,182176563686,147497146658,786575259172,809922390313,228908269659,
973967867901,579874670191,125850829414,276107572013,258976667806,661763361945,677932923662,717999289076,640442431523,656032966532,590457054595,416409509380,29284130688,
168848104208,5323300392,526319657599,790307412123,670316357228,14451351458,44944304007,184763758275}

{664062862940,371209195826,500760395677,213502574561,407987202195,618243198887,7507868706,982685603451,984624263743,184825285122,691193433687,794873502004,202552646911,
831121828034,117809838201,837979301727,944009960595,875730091573,928487129172,564008033283,19444951901,148407051399,902802383260,727695291915,401932019635,875612048370,
897127364705,602249064193,352855723818,640428054195,306092761693,743561916409,553098062995,711231338004,6626020059,954541653724,144164213750,882628116862,144064233877,
487423289003,627548663637,43271989230,345201595127,141248813704,135109517871}

Returns: 45

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.