10791  Minimum Sum LCM
Moderator: Board moderators
10791  Minimum Sum LCM
How about the following in/output?
in:
2342
2343
34
1
234
678
67223
76627567
334
787890
787611
0
out:
Case 1: 1173
Case 2: 104
Case 3: 19
Case 4: 2
Case 5: 31
Case 6: 119
Case 7: 5184
Case 8: 22408
Case 9: 169
Case 10: 131321
Case 11: 23900
Could someone give some critical case?
in:
2342
2343
34
1
234
678
67223
76627567
334
787890
787611
0
out:
Case 1: 1173
Case 2: 104
Case 3: 19
Case 4: 2
Case 5: 31
Case 6: 119
Case 7: 5184
Case 8: 22408
Case 9: 169
Case 10: 131321
Case 11: 23900
Could someone give some critical case?
I get:htl wrote: in:
2342
2343
34
1
234
678
67223
76627567
334
787890
787611
0
out:
Case 1: 1173
Case 2: 104
Case 3: 19
Case 4: 2
Case 5: 31
Case 6: 119
Case 7: 5184
Case 8: 22408
Case 9: 169
Case 10: 131321
Case 11: 23900
Case 1: 1173
Case 2: 85
Case 3: 19
Case 4: 2
Case 5: 24
Case 6: 118
Case 7: 5184
Case 8: 4829
Case 9: 169
Case 10: 26273
Case 11: 866

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
You have to use unsigned int for the result, since input can be: 2^31  1, so output is 2^31.
Last edited by Adrian Kuegel on Sun Dec 12, 2004 6:22 pm, edited 1 time in total.

 New poster
 Posts: 5
 Joined: Fri Dec 10, 2004 9:42 am

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Sure, for 4 the output should be 5.
Last edited by Adrian Kuegel on Sun Dec 12, 2004 8:18 pm, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
The idea is basically very simple. Say, the factorization of n is p1^q1 * p2^q2 * ... * pk^qk. Clearly, each pi^qi has to be a divisor of one of the numbers, otherwise the lcm of the numbers is not n. So in case of n = 4, the factorization is 2^2, so 4 has to be a divisor of one number. Now, since this specifies only one number, you have to add another one, and you have only the choice between 1,2 and 4. Clearly, 1 is the best choice (and it always is, if you have only one prime factor).