LCM (Least Common Multiple)

একটি সংখ্যা x কে অপর একটি সংখ্যা y দিয়ে ভাগ করলে যদি ভাগশেষ 0 থাকে, তবে x হবে y এর একটি গুণিতক (multiple). যেমন, 24 সংখ্যাটি 6 দিয়ে নিঃশেষে বিভাজ্য, তাই 6 এর একটি গুণিতক হবে 24. 

এখন দুটি সংখ্যা a ও b এর সাধারণ গুণিতক (common multiple) হবে এমন একটি সংখ্যা যেটি a ও b উভয় দিয়েই নিঃশেষে বিভাজ্য। যেমন, 24 সংখ্যাটি 6 ও 8 উভয় দিয়েই নিঃশেষে বিভাজ্য, 6 ও 8 এর একটি সাধারণ গুণিতক হবে 24.

এবার আমরা ধারণা করতেই পারছি যে, লঘিষ্ঠ সাধারণ গুণিতক (Least Common Multiple) হবে সংখ্যা দুটির সাধারণ গুণিতক গুলোর মধ্যে সবচেয়ে ছোট সংখ্যাটি। যেমন, 6 ও 8 এর গুণিতক গুলো হলো 24, 48, 72, 96 ইত্যাদি। এর মধ্যে সবচেয়ে ছোট গুণিতকটি হলো 24. তাই 6 ও 8 এর LCM (Least Common Multiple) হলো 24.

তাহলে আমরা শিখলাম LCM কী জিনিস। এবার আমরা শিখবো দুটি সংখ্যা a ও b এর LCM কিভাবে বের করতে হয়। LCM বের করার দুটি পদ্ধতি দেখবো আমরা। 

পদ্ধতি ১

প্রথমে আমরা a ও b উভয়ের prime factorization বের করবো। এখন কোনো prime factor p এর জন্য a ও b এর উভয়ের prime factorization এ p এর power যেখানে সর্বোচ্চ সেটিকে আমরা LCM এর prime factorization এ রাখবো। যেমন, 

6 এর prime factorization, 6 = 2 x 3

8 এর prime factorization, 8 = 2^3

তাহলে, এদের LCM এ 2 এর power হবে max (1,3) বা 3. আবার LCM এ 3 এর power হবে max(1,0) বা 1.

অতএব, 6 ও 8 এর LCM = 2^3 x 3 = 24.

পদ্ধতি ২

এই পদ্ধতি গতে দুটি সংখ্যার GCD ও LCM এর মধ্যকার সম্পর্কের উপর ভিত্তি করে আমরা তাদের LCM বের করবো। দুটি সংখ্যার গুণফল, তাদের GCD ও LCM এর গুণফলের সমান। অর্থাৎ দুটি সংখ্যা a ও b এর জন্য, 

a x b = GCD(a,b) x LCM(a,b).

তাহলে আমরা লিখতে পারি,

LCM(a,b) =(a x b) / GCD(a,b)

এখন আমরা যদি a ও b এর GCD জানি, তাহলে খুব সহজেই তাদের LCM বের করতে পারবো। 

উপরের দুটি পদ্ধতির মধ্যে প্রথমটিতে আমাদেরকে প্রদত্ত সংখ্যা দুটির prime factorization বের করতে হচ্ছে, যা খুবই time expensive. অন্যদিকে দ্বিতীয় পদ্ধতিতে GCD বের করলেই কাজ হয়ে যাচ্ছে। Prime factorization বের করার তুলনায় GCD বের করার time complexity খুবই কম। তাই আমরা program এ LCM বের করার প্রয়োজন হলে দ্বিতীয় পদ্ধতি অবলম্বন করবো। 

a ও b এর LCM বের করার code

//LCM(a,b) returns the LCM of a and b. int LCM (int a, int b){            int gcd = __gcd(a,b);      //GCD of a and b            int lcm = (a*b) / gcd;            return lcm; }

এখন আমাদেরকে যদি তিনটি সংখ্যা a,b ও c এর LCM বের করতে বলা হয়, তাহলে? এর জন্য আমরা প্রথমে a ও b এর LCM বের করব, এরপর তার সাথে c এর LCM বের করলেই সেটি হবে a, b ও c এর LCM. ঠিক একইভাবে আমরা n সংখ্যক integer জন্য LCM বের করতে পারি। 

তাহলে আমরা শিখে ফেললাম কিভাবে দুই বা ততোধিক সংখ্যার LCM বের করতে হয়। এবার আমরা একটু মাথা খাটিয়েই BEE 2514 ও BEE 1909 সমস্যা দুটির সমাধান করে ফেলতে পারি, তাই না?

BEE 2514

Problem link: https://www.beecrowd.com.br/judge/en/problems/view/2514

BEE 1909

Problem link: https://www.beecrowd.com.br/judge/en/problems/view/1909