ইউক্লিডিয়ান অ্যালগরিদম (GCD), Extended GCD

GCD - Greatest Common Divisor বাংলা: গরিষ্ঠ সাধারণ গুণনীয়ক(গ.সা.গু)। আমাদের দুইটি(বেশি ও হতে পারে) সংখ্যা দেয়া থাকবে, আমাদের  তাদের সব থেকে বড় divisor টি বের করতে হবে। অর্থাৎ আমাদের এমন একটি সংখ্যা বের করতে হবে যার থেকে বড় কোন সংখ্যা দিয়ে ওই সংখ্যা ওই সংখ্যাগুলোকে ভাগ করলে ভাগফল ০ না আসে।যেমন আমাদের বলা হল {১২,৬} এর গ.সা.গু কত? আমরা খুব সহজেই বলে দিতে পারি ৬।    

গ.সা.গু  বের করার অনেক উপায় আছে।  তার মধ্যে আমাদের ছোট বেলায় শিখা ইউক্লিড এর পদ্ধতি অনেক দ্রুত কাজ করে।
 gcd (a , b ) বের করার জন্য , চলুন ইউক্লিড এর পদ্ধতি টি একটু দেখে নিই:

•  a কে b দিয়ে ভাগ দিব, যদি a/b==0  হয় তাহলে এদের গ.সা.গু  b , ( b এর থেকে বড় কোন সংখ্যা b  কে ভাগ করতে পারে না)  

• যদি ভাগশেষ ০ না হয়, আমরা এমন একটি সহগ(coefficient)  c বের করব যেন, c = a - (b*t) অর্থাৎ c হল a,b  এর ভাগশেষ(a%b)।
• এখন আমরা gcd (b , c ) বের করব।  এবং আমরা আমাদের শেষ দুই ধাপ চালিয়ে যাব যতক্ষণ পর্যন্ত না  আমাদের কাঙ্খিত মান পাব।     

GCD বের করার recursive এলগোরিদম এর কোড হল: 

1.1: C++ implemention of GCD

 চাইলে এক লাইনের কোড ও লিখে ফেলতে পারি:

1.2: One line C++ implemention of GCD

এই এলগোরিদম এর টাইম কমপ্লেক্সিটি: O(min(a,b) )

Extended GCD  

GCD কিভাবে বের করতে হয় আমরা সেটা শিখে গেলাম, কিন্তু এখন যদি আমাদের বলা হয় a ও b  এর গ.সা.গু. যদি g হয় তাহলে x ও y এর এমন দুটি মান বের কর যেন ax + by  = g হয়। এ কে Extended GCD  বলা হয়। এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম এই ইউক্লিডীয়ান অ্যালগোরিদমেরই একটা এক্সটেনশন। এখানে আমরা gcd(a,b) এলগোরিদম কে কাজে লাগিয়ে ই egcd(a,b,x,y) এর মাধমে x ও y এর মান বের করব। শুধু প্রতিটি রিকার্সিভ কল এ x ও y এর মান পরিবর্তন করে দেব এইভাবে-  
x = y1 - [b/a] * x1
y = x1

1.3: C++ implemention of Extended GCD  

এই এলগোরিদম এর টাইম কমপ্লেক্সিটি: O(min(a,b)) 

  কনসেপ্টটা ঝালাই করে নিতে  প্রব্লেম দুটো সলভ করে ফেলি-

10090 – Marbles (UVA)
10104 – Euclid Problem(UVA)