Page 1 of 4
10791 - Minimum Sum LCM
Posted: Sun Dec 12, 2004 11:20 am
by htl
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?
Posted: Sun Dec 12, 2004 12:32 pm
by totster
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
Posted: Sun Dec 12, 2004 1:32 pm
by htl
I think I could understand your algorithm. But what's wrong with my program? Any critical case could cause error?
Posted: Sun Dec 12, 2004 2:01 pm
by krijger
I think you misunderstand the problem. The problem description reads:
a set of AT LEAST two positive integers
Posted: Sun Dec 12, 2004 2:13 pm
by htl
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.
Posted: Sun Dec 12, 2004 5:25 pm
by Adrian Kuegel
You have to use unsigned int for the result, since input can be: 2^31 - 1, so output is 2^31.
Posted: Sun Dec 12, 2004 6:17 pm
by unknown_error
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
Posted: Sun Dec 12, 2004 6:22 pm
by Adrian Kuegel
Sure, output is 2^31 in that case. Sorry for my typo.
Posted: Sun Dec 12, 2004 7:39 pm
by harry
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.
Posted: Sun Dec 12, 2004 7:54 pm
by Adrian Kuegel
But lcm of 2,3,3,13 is 78, so your result is wrong.
Posted: Sun Dec 12, 2004 8:09 pm
by harry
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
Posted: Sun Dec 12, 2004 8:11 pm
by Adrian Kuegel
Sure, for 4 the output should be 5.
Posted: Sun Dec 12, 2004 8:12 pm
by harry
now i am a bit confused.how can i get solution for such input.
Posted: Sun Dec 12, 2004 8:17 pm
by Adrian Kuegel
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).
Posted: Sun Dec 12, 2004 8:24 pm
by harry
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"