Aug 7, 2013
গ.সা.গু. - গরিষ্ঠ সাধারণ গুণণীয়ক (GCD - Greatest Common Divisor)
দুটি নাম্বারের GCD হল নাম্বার দুটির ফ্যাক্টরগুলোর মধ্যে সবচেয়ে বড় কমনফ্যাক্টরটি। আমরা জানি একটি নাম্বারের এক বা একাধিক ফ্যাক্টর থাকে। আমরাযদি দুটি নাম্বারের সবগুলো ফ্যাক্টর বের করি, এবং তাদের মধ্যে কমনফ্যাক্টরগুলোকে আলাদা করি, তাহলে সেই কমন ফ্যাক্টরগুলোর মধ্যে সবচেয়ে বড়টিইহবে নাম্বার দুটির GCD।
ধরা যাক, দুটি নাম্বার আছে, 12 এবং 16। নাম্বার দুটির ফ্যাক্টরগুলো দেখাযাক।
1 x 12 = 12 1 x 16 = 162 x 6 = 12 2 x 8 = 163 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। আমরা এদের প্রাইম ফ্যাক্টরাইজেশনবের করি।
যদি কোন একটিতে একটি প্রাইম ফ্যাক্টর না থাকে, যেমন উপরের উদাহরণে 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 - GCDLCM(GCD এবং LCM এর সম্পর্ক নিয়ে একটু চিন্তা করতে হবে!)
