It's been Long ago since I have posted my last post . Actually I am little Busy . After solving this problem I think I should make a Better Tutorial about solving this problem as Internet could not Provide you a better view to Solve this problem rather only the Source Codes . Here you will get better idea to solve this problem without watching any Source Codes. Although I solved it C++ . You can do it by C also . Here we go .
Clearance :
This is a very interesting problem about Prime Factorization, GCD & LCM . You can solve it using only Prime Factorization , or GCD , LCM . I solved it using Prime Factorization . So here I will share this Idea . I don't know what's the Condition about the GCD , LCM procedure . I thought this could Provide a TLE verdict or Inefficient approach but Prime factorization is the Base of GCD & LCM . So what the Problem said??
- You are given LCM(A,B) = C . You are given A & C . You have to find B [ That means You have a number & the LCM . You have to find the another number to get the LCM ]. If B exist the Print the 'B' else Print " NO SOLUTION".
- Here you Should know C should always be Divisible by A & B .[ Why ?? Then you must read what is LCM & Its Characteristics . Just Google it . ]
- So B will exist only when C is divisible A . Else print " NO SOLUTION ".
Finding B :
Now move to Find the' B ' from here. Remember you have to find Least ' B ' as ' B ' could be more than one. So how to find the answer .
- Do pre-generate a List of Prime upto Square Root of 10^7 using Sieve Of Eratosthenes before Scanning ( Taking Inputs ) number of test Cases .
- Then watch this.. How the LCM of two number can be Find. For Example LCM of 60, 16.
60 = 2*2*3*5 and 16 = 2*2*2*2 . So, LCM(60,16) = 2*2*2*2*3*5 = 240 . Look at Below's Image.How the LCM is 240 clear here.
LCM. Courtesy : AdminZero
- So the Prime Factors common & uncommon in Both we just take those Prime factors Multiplication . One thing is Notable here is : Consider the Amount ( Power ) of 2 at 60 ( 2 ) & 16 ( 4) . We take here the maximum 2's Power in the LCM that means 4 . Then consider the amount of 3 ( 0 , 1 ) & 5 ( 0, 1) .We take maximum amount of 3s & 5s in order to find LCM .
- So, now to Find B ( we have A=60 & C=240 ) let's take the Number of each Primes needed to Factorize A = 60 & C = 240 and then Compare the Power of Each Prime . For Example,
A (60) = 2 ^ 2 * 3^1 * 5^1 & C(240) = 2^4 * 3^1 * 5^1 .
Here Power of 2 [ A = 2 & C = 4 ] & Power of 3 [ A = 1 & C = 1 ] & Power of 5 [ A = 1 & C = 1 ]. ( We take here the Max Power Values of Primes of C compared to A. Not minimums & Equals . )
- Now to find B , lets take Those Prime's Power of ' C ' whose Prime's Power is greater than ' A ' and multiply to each Other . That will be the result of B .
SO, B for the Previous A ( 60 ) & C(240) is B = 2^4 ( The power 3 & 5 is same for both A & C .That's why we can't take that . )
- So, Here we get the Value of B .
========================= Hope You solved it Already ==================================
Code :
#include<bits/stdc++.h>
#define MAX 4000
#define LL long long int
using namespace std;
int status[(MAX/32)+10];
vector<int>primelist;
bool check(int n, int pos) { return (bool)(n & (1<<pos)); }
int SET(int n, int pos){ return n=n|(1<<pos);}
void sieve()
{
int sqrtN=int (sqrt(MAX));
/*for(int j=4; j<MAX; j=j+2)
status[j>>5]=SET(status[j>>5],j&31);*/
for(int i=3; i<=sqrtN; i=i+2)
{
if(check(status[i>>5],i&31)==0)
{
for(int j=i*i; j<=MAX; j= j + (i<<1))
{
status[j>>5]=SET(status[j>>5],j&31);
}
}
}
primelist.push_back(2);
int cnt = 1;
for(int i=3; i<=MAX; i=i+2)
{
if(check(status[i>>5], i&31)==0)
{
primelist.push_back(i);
}
}
//cout<<primelist.size()<<endl;
}
LL power(LL a, LL b)
{
if(b==0) return 1;
else return a*power(a, b-1);
}
LL solve( LL a, LL b)
{
LL ans = 1;
for(int i=0; i<550 && primelist[i]<=a && primelist[i]<=b; i++)
{
int cnta = 0, cntb = 0;
while(a%primelist[i]==0)
{
a = a/ primelist[i];
cnta++;
}
while(b%primelist[i]==0)
{
b = b/ primelist[i];
cntb++;
}
if(cntb>cnta) ans = ans * power(primelist[i], cntb);
}
if(b>1 && a==1) ans = ans * b;
return ans;
}
int main()
{
sieve();
int test;
LL a, c;
scanf("%d", &test);
while(test--)
{
scanf("%lld %lld", &a, &c);
if(c%a!=0)
printf("NO SOLUTION\n");
else
printf("%lld\n", solve(a, c));
}
return 0;
}
=> Thanks For reading . Have a Good Day .
=>Question about this Post or Need Help ?? Leave a Comment .
No comments:
Post a Comment