LCM Mania problem discussion on a approach

general
1

The contest starter 111 already ended.
Can anyone point out any error in my logic for solving the problem : “LCM MANIA”

I am iterating binarily by adding the value to x from n whenever I encounter a set-bit and y = n-x. Then I am checking if y is divisible by 2 and if lcm(y/2,x)==y/2,
then we can write a solution as 1 , y/2, x → Since this would return
lcm(1,y/2) = y/2
lcm(1,x)=x;
lcm(x , y/2) = y/2;
so the sum stands x + y/2 + y/2 = n;

I also checked for (x/2 ,y)

I checked for many numbers and it gives correct result, but it is not getting passed

eg: 10 → (1,2,4)
20 → (1,4,8)
etc. (sample cases got passed)
Here is my code logic:

void solve()
{
    ll n; cin>>n;
    if(n==1 || n==2) cout<<-1<<endl;
    else{
        ll g=n;
        ll x=0; ll id=0;
        while(g!=0){
            if(g%2==1) {
                x+=pow(2,id);
                ll y = n-x;
                if(y%2==0 && (y/2)%x==0) {cout<<1<<" "<<y/2<<" "<<x<<endl; return;}
                else if(x%2==0 && (x/2)%y==0) {cout<<1<<" "<<x/2<<" "<<y<<endl; return;}
            } 
            g/=2;
            id++;
        }
        cout<<-1<<endl;
    }
}
2

Your code doesn’t work for powers of 2, eg: 4, 8, 16.
The output contains 0 which isn’t a positive number

3

On powers of 2 you should return -1 but your code is giving 0 as one of the values of A,B,C which is not allowed. Instead of n==1 and n==2, write n&(n-1)==0.

1 Like
4

Oh, thanks. Got it

5

Yeah, got it. These should be -1.
such a silly mistake :cry: