ধর তোমাকে  Xn-কে M দ্বারা ভাগ করলে যে ভাগশেষ থাকে, সেটা বের করতে হবে। দেখতে খুবই সহজ এই প্রবলেমটাই বাস্তবে করতে গেলে অনেক ঝামেলার সৃষ্টি হয়ে যায়। আমরা সরাসরি যা করতে পারি তা হল প্রথমে Xn বের করে নিয়ে পরে ভাগশেষ তা বের করাঃ

Xn mod M = (Xn) % M

যেমনঃ

72 mod 4 = (72) % 4 = 49 % 4 = 1

73 mod 4 = (73) % 4 = 343%4 = 3

কিন্তু সমস্যা হল X কিংবা n-এর খুব ছোট মানের জন্যও X^n-এর বিশাল একটা মান চলে আসতে পারে, যা সি-এর ইন্টিজার বা অন্যান্য ডাটা টাইপের লিমিট ছাড়িয়ে যায়। এজন্যই আমাদের এখানে ব্যবহার করতে হয় Modulo Arithmetic!

Modulo Arithmetic-এ একটি সূত্র আছে এমনঃ

(ab)%M = {(a%M)(b%M)}%M

যেমন, 6*7%5 কে আমরা দুইভাবে বের করতে পারিঃ

6*7%5 = 42%5 = 2

আবার, Modulo Arithmetic-এর সাহায্যে করলেঃ

67%5 = {(6%5)(7%5)}%5 = (1*2)%5 = 2%5 = 2

এখন এই জিনিসটাই আমরা কাজে লাগাবো আমাদের সমস্যাটা সমাধান করতে! কিন্তু আমাদের হাতে আছে X^n… তাহলে আমাদের প্রথমেই একে দুইটি সংখ্যার গুণ-আকারে লিখতে হবে। আমরা এই কাজটা দুইভাবে করতে পারি, জোড় হলে একরকম, বিজোড় হলে আরেকরকম!

(n%2==0) হলে Xn = Xn/2 * Xn/2

অথবা Xn = X *  Xn-1

আবার n এর মান যদি ০ হয়, তাহলে তো কথায় নেই! এত ভাগ করার দরকার নেই, সরাসরিই রিটার্ন করে দিতে পারি,

X0 mod M = (1) mod M =  1 (কি মজা!)

 

এখন ধরা যাক n-এর ইনিশিয়াল ভ্যালু দেওয়া আছে ৪২, তাহলে আমরা ততক্ষণ লুপ চালাবো, যতক্ষণ না n-এর মান শূন্য হচ্ছে। এজন্য প্রথমে n-কে ২ দিয়ে ভাগ করে পাব ২১, তারপর ১ বিয়োগ করে পাবো ২০, তারপর ২ দিয়ে ভাগ করে ১০, আবার ভাগ করে ৫। এরপর ১ বিয়োগ করে ৪, তারপর ২ দিয়ে ভাগ করে ২, তারপর ২ দিয়ে ভাগ করে ১। এবং সবশেষে ১ বিয়োগ করলে আসবে ০।

কিন্তু আনন্দের ব্যাপার হল এর কোনোটাই আমাদেরকে করতে হবে না। আমরা একটা ফাংশন লিখে দিব, আর কম্পিউটার নিজেই এই কাজ করে আমাদের কাঙ্ক্ষিত মান রিটার্ন করে দিবে! তো চল, এবার ফাংশনটা লেখার চেষ্টা করা যাক!

 

আমাদের প্রথমেই তিনটা ভ্যারিয়েবল দরকারঃ X, n আর M… তাহলে এই তিনটা আমরা ফাংশনের প্যারামিটার হিসেবে নিব।

int mod(long long X,long long int n,long long int M ){

}

 

এরপর আমাদেরকে চিন্তা করা দরকার n-এর কোন মানের জন্য সরাসরি একটা কিছু রিটার্ন করে দিতে পারি। এই মানটা হল শূন্য! n-এর মান শূন্য হলে X^n % M রিটার্ন করবে 1. তাহলে আমরা লিখে ফেলিঃ

int mod(long long X,long long int n,long long int M ){
    if (n==0) return 1;

}

 

এখন আমাদের দুই ধরণের কেস নিয়ে কাজ করতে হবে। যদি n জোড় হয় আর যদি n বিজোড় হয়। যদি n বিজোড় হয় তাহলে আমরা X%M এর মান সরাসরি বের করে X^(n-1) % M -এর মান বের করার জন্য ফাংশনটাকে আবার কল করে দিব!

 

int mod(long long X,long long int n,long long int M ){
   if (n==0)return 1;
   if (n%2) return ((X%M)*(mod(X,n-1,M )))%M;

}

 

 

এবার জোড়ের পালা। জোড়ের ক্ষেত্রে আমাদেরকে {X^(n/2)%M * X^(n/2)%M}%M বের করতে হচ্ছে। তাহলে,

long long int mod ( long long X, int n, int M){
   if ( n == 0 )return 1;
   if ( n % 2 ) return ((X%M)*(mod(X,n-1,M)))%M;

   else  return (( (mod(X,n/2,M))%M)*( (mod(X,n/2,M))%M))%M;
}

 

 

কিন্তু আমরা এখানে বোকার মত (mod(X,n/2,M) বের করেছি দুই বার, তাও আবার রিকার্সিভ ফাংশন ডেকে ডেকে! এটা না করে আমরা (mod(X,n/2,M) কে আগে একটি ভ্যারিয়েবলে রাখতে পারি! তাহলে কোডটা হবে এমনঃ

long long int mod(long long int X, long long int n, long long int M) {
   if (n==0) return 1;
   if (n%2) return ((X%M) * mod(X,n-1,M)) %M;
   else {
   long long int d = mod(X,n/2, M);
   return ((d%M) * (d%M))%M;
   }
}

 

 

তাহলে এবার একটা মেইন ফাংশন লিখে ফেলা যাক এবং চেক করে নেওয়া যাক আমাদের mod ফাংশন ঠিকভাবে কাজ করছে কি না!

#include <stdio.h>
   long long int mod(long long int X, long long int n, long long int M) {
   if (n==0) return 1;
   if (n%2) return ((X%M) * mod(X,n-1,M)) %M;
   else {
      long long int d = mod(X,n/2, M);
      return ((d%M) * (d%M))%M;
   }
}

int main() {
   long long int a,b,c;
   scanf("%lld %lld %lld", &a,&b,&c);
   printf("%lld\n", mod(a,b,c));
   return 0;
}

 

 

এবার এভাবে তোমরা UVA 374 – Big Mod আর UVA 1230 – Modex  প্রবলেম সলভ করে ফেলতে পার! 🙂 হ্যাপি কোডিং!

Muntasir Wahed

Muntasir Wahed

System Administrator at স্বশিক্ষা.com
Jack of all trades, master of none.
Muntasir Wahed
Muntasir Wahed