গ.সা.গু. এবং ল.সা.গু. (GCD and LCM)

Aug 7, 2013

গ.সা.গু. - গরিষ্ঠ সাধারণ গুণণীয়ক (GCD - Greatest Common Divisor)

দুটি নাম্বারের GCD হল নাম্বার দুটির ফ্যাক্টরগুলোর মধ্যে সবচেয়ে বড় কমন ফ্যাক্টরটি। আমরা জানি একটি নাম্বারের এক বা একাধিক ফ্যাক্টর থাকে। আমরা যদি দুটি নাম্বারের সবগুলো ফ্যাক্টর বের করি, এবং তাদের মধ্যে কমন ফ্যাক্টরগুলোকে আলাদা করি, তাহলে সেই কমন ফ্যাক্টরগুলোর মধ্যে সবচেয়ে বড়টিই হবে নাম্বার দুটির GCD।

ধরা যাক, দুটি নাম্বার আছে, 12 এবং 16। নাম্বার দুটির ফ্যাক্টরগুলো দেখা যাক।

1 x 12 = 12        1 x 16 = 16
2 x  6 = 12        2 x  8 = 16
3 x  4 = 12        4 x  4 = 16

তাহলে 12 এর ফ্যাক্টরগুলো হল, 1, 2, 3, 4, 6, 12 এবং 16 এর ফ্যাক্টরগুলো হল, 1, 2, 4, 8, 16। এদের মধ্যে কমন ফ্যাক্টরগুলো হল, 1, 2, 4। অতএব 12 এবং 16 এর GCD হল 4।

প্রাইম ফ্যাক্টরাইজেশনের মাধ্যমেও আমরা GCD নির্ণয় করতে পারি। আমরা জানি প্রত্যেকটি নাম্বারকেই এক বা একাধিক প্রাইম নাম্বারের গুণফল আকারে প্রকাশ করা যায়। যেমন,

\[\begin{align*} 80 & = 2 \times 2 \times 2 \times 2 \times 5 = 2^{4} \times 5^{1}\\ 360 & = 2 \times 2 \times 2 \times 3 \times 3 \times 5 = 2^{3} \times 3^{2} \times 5^{1} \end{align*}\]

এখানে 80 এবং 360 এর GCD হবে,

GCD( 80, 360 ) = 2 x 2 x 2 x 5 = 40

ফ্যাক্টরাইজ করার মাধ্যমেই এটা দেখানো যায়। তবে উত্তরটি কিভাবে আসলো এবার দেখা যাক। ধরা যাক দুটি নাম্বার, a এবং b। আমরা এদের প্রাইম ফ্যাক্টরাইজেশন বের করি।

\[\begin{align*} a & = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times p_{3}^{a_{3}} \times \ldots \times p_{n}^{a_{n}}\\ b & = p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times p_{3}^{b_{3}} \times \ldots \times p_{n}^{b_{n}} \end{align*}\]

যদি কোন একটিতে একটি প্রাইম ফ্যাক্টর না থাকে, যেমন উপরের উদাহরণে 360 এর ক্ষেত্রে 3 আছে কিন্তু 80 এ 3 নেই, তার মানে সেখানে 3 এর ঘাত আসলে 0। অতএব, a1, a2, …, an এবং b1, b2, …, bn এদের মান 0 হতে পারে। এখন প্রাইম ফ্যাক্টরাইজেশন করা হয়ে গেলে, এদের GCD এর মান হবে নিম্নরূপঃ

\[GCD( a, b ) = p_{1}^{min( a_{1}, b_{1} )} \times p_{2}^{min( a_{2}, b_{2} )} \times p_{3}^{min( a_{3}, b_{3} )} \times \ldots \times p_{n}^{min( a_{n}, b_{n} )}\]

80 এবং 360 এর GCD নির্ণয়ের ক্ষেত্রে আসলে এটাই করা হয়েছে।

\[\begin{align*} 80 & = 2^{4} \times 3^{0} \times 5^{1} \\ 360 & = 2^{3} \times 3^{2} \times 5^{1}\\ GCD( 80, 360 ) & = product \hspace{2 pt} of \hspace{2 pt} all \hspace{2 pt} the \hspace{2 pt} common \hspace{2 pt} prime \hspace{2 pt} factors\\ & = 2^{min( 4, 3 )} \times 3^{min( 0, 2 )} \times 5^{min( 1, 1 )}\\ & = 2^{3} \times 3^{0} \times 5^{1} = 40 \end{align*}\]

এভাবে উত্তর পাওয়া যায় কারণ কোন একটা নাম্বারের সবগুলো ফ্যাক্টরই তার প্রাইম ফ্যাক্টরগুলোর বিভিন্ন কম্বিনেশন থেকে পাওয়া যায়। তবে খেয়াল রাখতে হবে কোন প্রাইম ফ্যাক্টর মূল নাম্বারে যতবার আছে তার চেয়ে বেশিবার নেওয়া যাবে না। অতএব যখন কমন ফ্যাক্টর বের করতে হয় তখন কমন প্রাইম ফ্যাক্টরগুলো বিভিন্ন কম্বিনেশনে নিলেই হয়ে যাচ্ছে। কিন্তু আমাদের উদ্দেশ্য হল সবচেয়ে বড় কমন ফ্যাক্টর বের করতে হবে। তাই আমরা কমন প্রাইম ফ্যাক্টরগুলোর সবগুলো নিব। তাহলেই GCD পেয়ে যাচ্ছি।

প্রোগ্রামিং এর ক্ষেত্রে এভাবে ফ্যাক্টরাইজ করে GCD বের করা খুবই সময়সাপেক্ষ এবং কষ্টসাধ্য একটি কাজ। এই জন্য GCD বের করার আরেকটি এলগোরিদম রয়েছে যেটিকে ইউক্লিডের এলগোরিদম বলা হয়। গ্রিক গণিতবিদ ইউক্লিড এই এলগোরিদমের আবিষ্কারক।

ইউক্লিডের এলগোরিদম

ইউক্লিডের এলগোরিদমের বেসিক কনসেপ্টই এসেছে আমাদের ছোটবেলার শেখা ভাগ করার সূত্র থেকে।

আমরা জানি, ভাজ্য = ভাজক x ভাগফল + ভাগশেষ

এটাকে আমরা লিখতে পারি, a = bq + r, যেখানে a, b, q, r সকলেই পূর্ণ সংখ্যা (integer) এবং এখান থেকে বলা যায়, GCD( a, b ) = GCD( b, r )। এটাই এলগোরিদমের মূল কথা। এখন ব্যাখ্যায় আসা যাক।

একটা উদাহরণ দেখি। দুটি নাম্বার 84 এবং 196। এবার আমরা ছোট নাম্বারটি দিয়ে বড়টিকে ভাগ করব।

196 = 84 x 2 + 28

এখানে, a = 196, b = 84, r = 28। আমাদের নিয়ম অনুসারে GCD( 196, 84 ) = GCD( 84, 28 ) হওয়ার কথা। একটু খেয়াল করলেই বোঝা যাবে বিষয়টা। 84 এবং 196 এর GCD হবে যে নাম্বারটি সেই নাম্বারটি দিয়ে 84 এবং 196 উভয়েই নিঃশেষে বিভাজ্য হবে। যেহেতু 196 = 84 x 2 + 28 তাই সেই নাম্বারটি দিয়ে যদি 84 এবং 196 উভয়কেই ভাগ যেতে হয় তাহলে নাম্বারটি দিয়ে 28 কেও ভাগ যেতে হবে। অন্যথায় 84 এবং 196 উভয়কে ভাগ করা সম্ভব না। অতএব GCD( 196, 84 ) = GCD( 84, 28 )।

এখন একই কাজ আবারও করি।

84 = 28 * 3 + 0

যেহেতু 28 দিয়ে 84 নিঃশেষে বিভাজ্য, তাই GCD( 84, 28 ) = 28 = GCD( 196, 84 )। অতএব যা দাঁড়ালো তা হল, আমরা বারবার এভাবে ভাগ করতে থাকব যতক্ষণ না ভাগশেষ 0 হয়। যখনই ভাগশেষ 0 হবে তখন b এর যে মান থাকবে সেটিই হবে আমাদের নির্ণেয় GCD। এবার এলগোরিদমটিকে কোডে লেখা যাক।

int GCD( int a, int b )
{
    int temp;
    if( a < b ) swap( a, b );
    while( a % b != 0 ) {
        temp = a;
        a = b;
        b = temp % b;
    }
    return b;
}

এছাড়াও আমরা রিকার্সিভ ফাংশনের মাধ্যমেও এটিকে লিখতে পারি।

int GCD( int a, int b )
{
    if( b == 0 ) return a;
    if( a < b ) swap( a, b );
    int r = a % b;
    return GCD( b, r );
}

এভাবে আমরা খুব সহজেই দুটি নাম্বারের GCD নির্ণয় করতে পারি। আর যদি দুইয়ের অধিক নাম্বার থাকে তাহলে তাদের দুটির GCD নির্ণয় করে সেই GCD এবং অপর একটি নাম্বারের GCD বের করে সেই GCD এবং অপর আরেকটি নাম্বারের GCD বের করব এবং যতক্ষণ না নাম্বার শেষ হবে ততক্ষণ একই কাজ করতে থাকব। যেমন, GCD( a, b, c, d ) = GCD( a, GCD( b , GCD( c, d ) ) ) ।

ল.সা.গু - লঘিষ্ঠ সাধারণ গুণিতক (LCM - Least Common Multiple)

দুটি সংখ্যার LCM হল তাদের গুণিতক সমূহের মধ্যে সাধারণ গুণিতকগুলোর সবচেয়ে ছোটটি। যেমন 2 এবং 3 যদি আমরা বিবেচনা করি তাহলে এদের গুণিতকগুলো হবে,

2 = 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, …
3 = 3, 6, 9, 12, 15, 18, 21, …
কমন গুণিতক = 6, 12, 18, …
LCM = 6

যেকোন দুটি নাম্বার, যদি তাদের কোনটি 0 না হয়, তাহলে তাদের একটি LCM থাকবেই। দুটি নাম্বারের LCM-ও আমরা প্রাইম ফ্যাক্টরাইজেশন থেকে বের করতে পারি। আবারও ধরা যাক দুটি নাম্বার a এবং b। তাহলে,

\[\begin{align*} a & = p_{1}^{a_{1}} \times p_{2}^{a_{2}} \times p_{3}^{a_{3}} \times \ldots \times p_{n}^{a_{n}}\\ b & = p_{1}^{b_{1}} \times p_{2}^{b_{2}} \times p_{3}^{b_{3}} \times \ldots \times p_{n}^{b_{n}} \end{align*}\]

এখন নাম্বার দুটির LCM হবে,

\[LCM( a, b ) = p_{1}^{max( a_{1}, b_{1} )} \times p_{2}^{max( a_{2}, b_{2} )} \times p_{3}^{max( a_{3}, b_{3} )} \times \ldots \times p_{n}^{max( a_{n}, b_{n} )}\]

এমনটি হওয়ার কারণ হল আমরা যদি একটি নাম্বার দ্বারা বিভাজ্য কোন নাম্বার পেতে চাই তাহলে নাম্বার দুটির সবগুলো প্রাইম ফ্যাক্টরকে গুণ করতে হবে এবং এক্ষেত্রে প্রতিটি ফ্যাক্টর মূল নাম্বারে যতবার আছে কমপক্ষে ততবার নিতে হবে। একারণে যখন দুটি নাম্বার দ্বারা বিভাজ্য কোন নাম্বার পেতে চাই তখন দুটিরই সবগুলো ফ্যাক্টর রাখতে হবে এবং সর্বাধিক যতবার আছে ততবার নিতে হবে। যদি আমরা 80 এবং 360 বিবেচনা করি তাহলে,

\[\begin{align*} 80 & = 2^{4} \times 3^{0} \times 5^{1}\\ 360 & = 2^{3} \times 3^{2} \times 5^{1}\\ LCM( 80, 360 ) & = 2^{4} \times 3^{2} \times 5^{1} = 720 \end{align*}\]

এমনটি হওয়ার কারণ হল যদি আমরা 2^4 এর স্থানে 2^3 নিতাম, সেটি 360 দিয়ে বিভাজ্য হলেও 80 দ্বারা বিভাজ্য হত না। আবার যদি 3^2 না নিয়ে 3^0 নিতাম তাহলে সেটি 80 দ্বারা বিভাজ্য হলেও 360 দ্বারা হত না।

তবে প্রোগ্রামিং এর ক্ষেত্রে এভাবে LCM নির্ণয় করা বেশ সময়সাপেক্ষ। এজন্য GCD এবং LCM এর মধ্যে একটি সম্পর্ক রয়েছে যার সাহায্যে LCM নির্ণয় করা হয়।

GCD ও LCM এর মধ্যে সম্পর্ক এবং LCM নির্ণয়

\[\begin{align*} GCD(a,b) \times LCM(a,b) & = | a \times b |\\ LCM(a,b) & = \frac{| a \times b |}{GCD(a,b)} \end{align*}\]

int LCM( int a, int b )
{
    int m = abs( a * b ); // abs() পরম মান রিটার্ন করে
    return m / GCD( a, b );
}

এভাবে পূর্বে লেখা GCD() ফাংশনটির সাহায্যে আমরা সহজেই LCM নির্ণয় করতে পারি।

প্র্যাকটিস প্রবলেমঃ
১। UVa 11417 - GCD (একেবারেই সাধারণ একটি প্রবলেম)
২। UVa 11388 - GCD LCM (GCD এবং LCM এর সম্পর্ক নিয়ে একটু চিন্তা করতে হবে!)