LCMMANIA - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: indreshsingh
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Math

PROBLEM:

Given N, find integers A, B, C such that N = \text{lcm}(A, B) + \text{lcm}(B, C) + \text{lcm}(A, C) or claim that none exist.

EXPLANATION:

If you work out a few cases by hand, or perhaps run a bruteforce for small N, you might see that only N = 2^k don’t have solutions.
This is indeed true.

Why?

Let A, B, C be three positive integers.
Let \gcd(A, B, C) = g, \gcd(A, B) = gx, \gcd(A, C) = gy, \gcd(B, C) = gz.
Then, it can be seen that x, y, z are all pairwise coprime; and further

A = gxya \\ B = gxzb \\ C = gyzc

where a,b,c are also pairwise coprime (do you see why?).

Now, direct substitution and cancellation shows that

\text{lcm}(A, B) + \text{lcm}(B, C) + \text{lcm}(A, C) = gxyz\cdot (ab + ac + bc)

Since a,b,c are pairwise coprime, at most one of them can be even - which tells us that (ab+bc+ac) is odd.
So, \text{lcm}(A, B) + \text{lcm}(B, C) + \text{lcm}(A, C) will have an odd factor that’s \gt 1, which means it can’t be a power of 2.

For non-powers-of-2, here’s a fairly simple construction that works:

  • If N = 2k+1 is an odd number that’s \gt 1, take the triple (k, 1, 1).
    This gives \text{lcm}(A, B) + \text{lcm}(B, C) + \text{lcm}(A, C) = k + 1 + k = 2k+1 = N.
  • If N is even and not a power of 2, we can write N = 2^m \cdot x, where x is an odd number \gt 1.
    Let x = 2y+1. From the previous point, we know (y, 1, 1) is a solution for it.
    Multiplying everything by 2^m gives us (2^m\cdot y, 2^m, 2^m) as a solution for N.

TIME COMPLEXITY:

\mathcal{O}(\log N) per testcase.

CODE:

Author's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int               long long
#define pb                push_back
#define ppb               pop_back
#define pf                push_front
#define ppf               pop_front
#define all(x)            (x).begin(),(x).end()
#define fr                first
#define sc                second
#define rep(i,a,b)        for(int i=a;i<b;i++)
#define ppc               __builtin_popcount
#define ppcll             __builtin_popcountll
#define debug(x)  cout<<(x)<<'\n';
#define vi                vector<int>

const long long INF=1e18;
const int32_t M=1e9+7;
const int32_t MM=998244353;

const int N=0;



void solve(){
   
int n;
cin>>n;

int temp=n;
int k=0;
while(temp)
{   k++;
    temp=temp/2;
}

if((1<<(k-1))==n)
{
    cout<<-1<<'\n';
    return;
}
if(n%2==1)
{
    cout<<n/2<<" "<<1<<" "<<1<<'\n';
    return;
}
temp=n;
k=0;
while(temp%2==0)
{   k++;
    temp=temp/2;
}
cout<<temp/2*(1<<k)<<" "<<(1<<k)<<" "<<(1<<k)<<'\n';
    



    
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);

    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n = int(input())
    mul = 1
    while n%2 == 0:
        n //= 2
        mul *= 2
    if n == 1: print(-1)
    else: print(mul*(n//2), mul, mul)
3 Likes
2

can someone explain how did A=g.x.y.a. ? happen

3

A has several factors where g is common with all A, B,C, x is common with A,B but not with C, y is common with A,C but not with B, a is not common with anyone
And hence A is product of all its factors gxyz

4

include <bits/stdc++.h>
using namespace std;
define int long long
const int mod = 1e9 + 7;

signed main(){

ios::sync_with_stdio(false);
cin.tie(nullptr);

int t;
cin>>t;
while(t–){
int n; cin>>n;
if((n<3) || ((n & (n-1)) == 0)) cout<<-1<<endl;
else if(n%3==0) cout<<n/3<<" “<<n/3<<” “<<n/3<<endl;
else if(n&1){
cout<<1<<” “<<1<<” “<<(n-1)/2<<endl;
}
else{
cout<<2<<” “<<2<<” "<<(n-2)/2<<endl;
}
}
return 0;
}
Could anyone help whats wrong with this code it is generating the correct triplet as far as I tested on my testcases still codecheff showing wrong answer.

5

Your code will not work for several cases. One such case is n = 12.
Your code will give output (2,2,5) but lcm(2,2) = 2 , lcm(2,5) = 10 so 2,2,5 is answer of 2+10+10 = 22 and not 12.

8

I had a different idea but it almost produces the same answer and is fast enough to pass.
Claim: You can always have the answer in the form:
1 , (N-2*X) , X if the answer exists [The answer only exists if N-2*X is a non-zero divisor of X]

Proof: well it’s easy to see LCM(1, X) + LCM(N- 2 * X, X) + LCM(1, N-2 * X) = X + X + N - 2 * X = N.

    cin >> n;
    debug(n)
    if(n<3) {
        cout << -1 << nl; return;
    }
    if(n & 1) {
        cout << "1 1 " << n/2 << nl;
        return;
    }
    if(n%3==0) {
        rep(i, 3) cout << n / 3 << sp; cout << nl;
        return;
    }
    int x = n/2-((n/2)%2?1:0);
    debug(x)
    while(x >= (n-2*x)) {
        if((n-2*x) && x%(n-2*x)==0) {
            cout << 1 << sp << n-2*x << sp << x << nl;
            return;
        }
        x-=2;
    }
    cout << -1 << nl