10791 - Minimum Sum LCM

htl · Post by **htl** » Sun Dec 12, 2004 11:20 am

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?

totster · Post by **totster** » Sun Dec 12, 2004 12:32 pm

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

I get:

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

htl · Post by **htl** » Sun Dec 12, 2004 1:32 pm

I think I could understand your algorithm. But what's wrong with my program? Any critical case could cause error?

krijger · Post by **krijger** » Sun Dec 12, 2004 2:01 pm

I think you misunderstand the problem. The problem description reads:

a set of AT LEAST two positive integers

htl · Post by **htl** » Sun Dec 12, 2004 2:13 pm

I have modified my code that I get the same answer as above. But I still got WA. I don't know what I haven't paid attention to.

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Dec 12, 2004 5:25 pm

You have to use unsigned int for the result, since input can be: 2^31 - 1, so output is 2^31.

unknown_error · Post by **unknown_error** » Sun Dec 12, 2004 6:17 pm

for input 2^31-1 the output is 2^31. so, it's better to use unsigned int or long long .. for this silly mistake i needed 5 submission during the contest to get AC

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Dec 12, 2004 6:22 pm

Sure, output is 2^31 in that case. Sorry for my typo.

harry · Post by **harry** » Sun Dec 12, 2004 7:39 pm

hi totster.
should the answer of 234 be 21.
you have write for 234 , 24
atleat i can say that 234=2*3*3*13,then sum =21.

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Dec 12, 2004 7:54 pm

But lcm of 2,3,3,13 is 78, so your result is wrong.

harry · Post by **harry** » Sun Dec 12, 2004 8:09 pm

what abt 4
4 = 4,since 2*2=4 but lcm of 2,2=2;//corrcted
or 4 = 5, 4*1=4,4+1=5

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Dec 12, 2004 8:11 pm

Sure, for 4 the output should be 5.

harry · Post by **harry** » Sun Dec 12, 2004 8:12 pm

now i am a bit confused.how can i get solution for such input.

Adrian Kuegel · Post by **Adrian Kuegel** » Sun Dec 12, 2004 8:17 pm

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).

harry · Post by **harry** » Sun Dec 12, 2004 8:24 pm

thanks adrian . i was thinking in a wrong way.i forgot to consider
"Clearly, each pi^qi has to be a divisor of one of the numbers"