10791  Minimum Sum LCM
Moderator: Board moderators
Output when N=1
I got lots of wrong answers in this problem when n=1.
(I was answering 0 and in a later submission 1)
I think n=1 shouldn't be a valid input. (altough in description it's stated as that).
When n=1 there aren't 2 integers which lcm gives 1.
I just saw in this board that when n=1, output should be 2.
(1*1 = 1 , 1+1=2)...
But I don't think the output should be 2. It doesn't make sense... (since {1,1} is not a set).
Any comments on this ?
(I was answering 0 and in a later submission 1)
I think n=1 shouldn't be a valid input. (altough in description it's stated as that).
When n=1 there aren't 2 integers which lcm gives 1.
I just saw in this board that when n=1, output should be 2.
(1*1 = 1 , 1+1=2)...
But I don't think the output should be 2. It doesn't make sense... (since {1,1} is not a set).
Any comments on this ?

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Precisely because {1,1} is no set I can not see the logic of 2 being the answer.
The problem description requires the numbers to sum to be different.
What arguments do you have for 2 being a better answer than 0 ?
0 seems the best answer since there's no solution. (no set, so the sum is 0)
Anyway, I think the problem should be revised to exclude 1 from being a valid input.
The problem description requires the numbers to sum to be different.
What arguments do you have for 2 being a better answer than 0 ?
0 seems the best answer since there's no solution. (no set, so the sum is 0)
Anyway, I think the problem should be revised to exclude 1 from being a valid input.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
Sure, theoretically there is no solution. But why should 0 indicate the value of no solution? You have arbitrarily chosen 0.
Since the problemsetter didn't define anything that should indicate a "no solution", we have to assume he thinks there is always a solution. Now, 2 makes more sense as output for 1, since if we assume the problemsetter thought of a multiset when he wrote his problem description, this would be the output.
I don't want to say that 2 is the correct output for 1, I only tried to show how you can find a way to get accepted systematically in cases where the problemsetter made a mistake.
And in my opinion, the description should only change set to multiset, then everything is ok.
Since the problemsetter didn't define anything that should indicate a "no solution", we have to assume he thinks there is always a solution. Now, 2 makes more sense as output for 1, since if we assume the problemsetter thought of a multiset when he wrote his problem description, this would be the output.
I don't want to say that 2 is the correct output for 1, I only tried to show how you can find a way to get accepted systematically in cases where the problemsetter made a mistake.
And in my opinion, the description should only change set to multiset, then everything is ok.

 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
10791. Why WA ???
I really can't understand what's wrong with my code...
I think I take care of everything, but I still got WA
here is my code:
thanks to everyone!
I think I take care of everything, but I still got WA
here is my code:
Code: Select all
#include <stdio.h>
unsigned long res=0;
calc(unsigned long n){
int i,j,sum=1;
while(n%2==0){
n=n/2;
sum*=2;
}
if (sum>1){
res+=sum;
sum=1;
}
i=3;
while(i*i<=n){
while(n%i==0){
n=n/i;
sum*=i;
}
if(sum>1) {
res+=sum;
sum=1;
}
i+=2;
}
res+=n;
if(res==n)
return 0;
return 1;
}
int main()
{
unsigned long n;
int c=0;
while(scanf("%lu",&n)&n!=0){
c++;
if(calc(n))
printf("Case %d: %lu\n",c,res);
else
printf("Case %d: %lu\n",c,n+1);
res=0;
}
return 0;
}
first of all
I am so sorry...for the waiting
shamim:
the algorithm just take the input number, it factorize in primes, and for every prime it factorize it sums to the result...I mean for example
24=2^3 * 3
so there are three 2's so one of the numbers that must stay is 8 because the LCM are the common and not common factors of all the numbers
and the other is the 3
another example
1575: 3^2 * 5^2 * 7
so the numbers that have to appear to form 1575 as LCM are {9, 25,7}
so the sum must be 41
sorry but my english is so bad so it is difficult to explain what I think in english...
Now I have no time, but tomorrow I would make a better explanation of this just to the people that want some help with this problem
prince56k:
Thank you so much for this great help, tomorrow I will debug my code so it works fine...
byee and sorry again for the waiting!
I am so sorry...for the waiting
shamim:
the algorithm just take the input number, it factorize in primes, and for every prime it factorize it sums to the result...I mean for example
24=2^3 * 3
so there are three 2's so one of the numbers that must stay is 8 because the LCM are the common and not common factors of all the numbers
and the other is the 3
another example
1575: 3^2 * 5^2 * 7
so the numbers that have to appear to form 1575 as LCM are {9, 25,7}
so the sum must be 41
sorry but my english is so bad so it is difficult to explain what I think in english...
Now I have no time, but tomorrow I would make a better explanation of this just to the people that want some help with this problem
prince56k:
Thank you so much for this great help, tomorrow I will debug my code so it works fine...
byee and sorry again for the waiting!