UVA – 11388 – GCD LCM

Problem link

আলোচনাঃ
আমাকে দুইটা সংখ্যা (ধরি g,l) দেয়া হবে, আমাকে এমন দুইটা সংখ্যা (a,b) নির্ণয় করতে হবে যাদের gcd হবে g এর সমান, আর lcm হবে l এর সমান।

উত্তরঃ
তাহলে যদি উত্তর থাকে তবে, আমাদের উত্তর g,l -ই হবে। কারণ প্রশ্নে বলাই আছে, gcd(a,b)=g and lcm(a,b)=l হবে। তাহলে আমরা দেখতে পারি g,l এর gcd ও lcm কত হয়। যদি gcd(g,l)=g and lcm(g,l)=l হয় তাহলে g,l print করতে পারি। আর যদি g,l এর সমান না হয় তবে -1 print করতে হবে।

C++ Code:

#include<bits/stdc++.h>
using namespace std;

int main(){
   int t;
   scanf("%d",&t);
   for(int i=1;i<=t;i++){
        int g,l;
        scanf("%d%d",&g,&l);
        int gcd=__gcd(g,l); // O(logN) ,  where N = max(g,l)
        int lcm=(g/gcd)*l;  // O(1)
        if(gcd==g && lcm==l)
            printf("%d %d\n",gcd,lcm);
        else printf("-1\n");
        
   }
}

Leave a Reply