In this problem, The LCM (A, B, C) = L
and Here A , B , L
are known you can findC
which 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.
The LCM (A, B, C) = L
and A, B, L
are 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 ofX
that 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 multiplyC
by the difference of its exponents, so as to guarantee X / GCD(C, X)
Will not eliminate the "useful" prime factors in X
.
#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