Problem Name: Finding LCM

LightOj-1215

Solution Idea:

In this problem, The LCM (A, B, C) = L and Here A , B , Lare known you can findCwhich is the smallest number of all satisfyingC.
We know that,
GCD of two value is smallest power of their prime factorization.
LCM of two value is highest power of their prime factorization.

Solution Approach:

The LCM (A, B, C) = Land A, B, Lare known .
Simplify LCM (A, B, C) = L is LCM(LCM(A,B),C)=L.
Let, X= LCM(A,B)so LCM(X, C)=L
Now, If L is not divisible by X then it is impossible to find anyC.
Otherwise find smallest C which satisfies LCM(X, C)=L.
We get C which prime factors ofXthat do not belong toL.
But in order to make X / GCD(C, X) * C == L , we need to find the common prime factor of X and C, and multiplyCby the difference of its exponents, so as to guarantee X / GCD(C, X) Will not eliminate the "useful" prime factors in X.

Cpp Code:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll t;
    cin >> t;
    ll i = 1;
    while (t--)
    {
        ll A, B, L;
        cin >> A >> B >> L;
        ll X = A*B / gcd(A, B);
        if (L % X != 0) cout << "Case " << i++ << ": impossible" << '\n';
        else
        {
            ll C = L / X;
            ll g = gcd(C, X);
            while (g != 1)
            {
                C *= g;
                X /= g;
                g = gcd(C, X);
            }

            cout << "Case " << i++ << ": " << C << '\n';
        }
    }
}

Happy Coding!

Written by: Md. Rasel Meya

Tutorial source