LightOJ - 1215 - Finding LCM

Ideas : LCM(a,b,c)= L ,here a, b, L are given and we have to find the value of c. LCM of two value is maximum power of their prime factorization.So,we need to prime factorize a,b, and L then compare their power if any prime factor power of L is greater than power of a and b  then it is from c.

Code First Then See Solutions

Code: 

#include <bits/stdc++.h>

using namespace std;

#define mx 1000007

#define ll long long

bitset <mx> b;

vector <ll> v;

void seive()

{

    b.set();

    b[0]=b[1]=false;

    for(ll i=0;i<mx;i++)

    {

        if(b[i])

        {

            v.push_back(i);

            for(ll j=i*i;j<=mx;j+=i)

                b[j]=false;

        }

    }

}

int main()

{

    int t,f=0;

    seive();

    cin>>t;

    while(t--)

    {

        f++;

        long long a,b,l,gcd,lcm,res=1;

        cin>>a>>b>>l;

        if(l%a!=0||l%b!=0)

        {

           cout<<"Case "<<f<<": "<<"impossible"<<endl;

           continue;

        }

        gcd=__gcd(a,b);

        lcm=(a*b)/gcd;

        for(int i=0;v[i]<=l&&i<v.size();i++)

        {

            if(l%v[i]==0)

            {

                int cnt1=0;

                while(l%v[i]==0)

                {

                    cnt1++;

                    l/=v[i];

                }

                int cnt2=0;

                while(lcm%v[i]==0)

                {

                    cnt2++;

                    lcm/=v[i];

                }

                if(cnt1>cnt2)

                {

                    for(int j=0;j<cnt1;j++)

                        res*=v[i];

                }

            }

        }

        cout<<"Case "<<f<<": "<<res<<endl;

    }

    return 0;

}