বিগ মোড থিওরিয়াম।

***********আমরা কিভাবে 45^434%23=? নির্ণয় করব?**********

প্রথমে মনে করি এই সমস্যাটির কথা ৬*৪%৩=? । তাহলে আমরা এখন সমাধান করে ফেলি এই প্রবলেমটির। প্রথমে আমরা নিম্নক্ত ভাবে প্রবলেমটির সমাধান করব। ৬*৪%৩ = ২৪%৩ = ০। অর্থাৎ উত্তর হচ্ছে ০। আমরা এই প্রবলেমটির আরেকভাবে সমাধান করতে পারব।দেখি এখন কিভাবে সমাধান করা যায় তাহলে। ((৬%৩)*(৪%৩))%৩ = (০*১)%৩ = ০। অর্থাৎ যদি a*b%c হয় তাহলে আমরা বলতে পারি যে ((a%c)*(b%c)%c) অর্থাৎ আমরা এই ফরমুলায় ফেলে তাহলে এই ৫৬৭*২৩৪%৩৪=?সমস্যাটিরও সমাধান করতে পারব। এখানে যদি ধরি a = ৫৬৭ , b = ২৩৪ , এবং c = ৩৪ হয়। তাহলে সমাধান করে আপনারা দেখতে পারেন ((a%c)*(b%c)%c) এই ফরমুলাটি ব্যাবহার করে।

তাহলে আমরা এটা জানতে পারলাম যে ((a%c)*(b%c)%c) ফরমুলাটি ব্যাবহার করে আমরা a*b%c এই ধরনের প্রবলেম এর সমাধান করতে পারব।

কিন্তু আমরা চাচ্ছি যে 45^434%23=??

এটা আমরা কিভাবে নির্ণয় করব? এটা করার জন্যে আমাদের যেটা করতে হবে তা হল আমাদের এই প্রবলেম টিকে ঐ ফরমুলায় রূপান্তর করতে হবে। এটা কিভাবে করা যাবে এখন তা বলার চেষ্ট্রা করব । ধরি a^b%c=? এখন আমরা a^b কে নিশ্চয় a^(b/2)*a^(b/2) এইভাবে লিখতে পারি। তাহলে আমাদের প্রবলেম টির ফরমুলাটি প্রায় হয়েই গেছে এবং তা হচ্ছে এমনঃ a^b%c=((a^(b/2)%c)*(a^(b/2)%c))%c কিন্তু a এবং b সংখ্যাটি যদি অনেক বড় কোন সংখ্যা এবং বিজোড় সংখ্যা হয় তাহলে এটা অবশ্যই এখনও অনির্নীয় ঐ থেকে যাবে এবং b যদি বেজোড় কোন সংখ্যা হয় তাহলে প্রবলেমটিতে দশমিক মান চলে আসবে যা আসলে আমাদের সঠিক রেজাল্ট পাওয়া সম্ভব নয়।

তাহলে আমরা দেখি আর কোন ভাবে a^b কে আমরা উপস্থাপন করতে পারি কিনা যাতে আমাদের উপরিউক্ত প্রবলেম টি সমাধান করতে পারি।

a^b = a*a^(b-1) এই ফরমুলায় ফেলতে পারি যা আমরা যদি ((a%c)*(b%c)%c) এই ফরমুলায় প্রকাশ করি তাহলে আমাদের ফরমুলাটি হবে নিম্নের মতন।

((a%c)*(a^(b-1))%c)%c এখন যদি এই ফরমুলায় দেখি তাহলে এখানে দুইটি অংশ দেখতে পাব একটি অংশতে আমরা সমাধান পাব আরেকটিতে পাবনা। a%c এখানে solvable a^something unsolvable

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

এখানে বেস কেস টি হবে

if(b==0)
  return 1;
  

you can see this code to understand better. if you know about recursion i think you will understand this code. if you don't understand this code after hard thinking then you can ask me. I will try my best. This code here.

#include

 

int Exmod(int a,int b,int c){

if(b==0)

return 1;

else if(b%2==0){

int d = Exmod(a,b/2,c);

return (d*d)%c;///for (a^b/2%c)*(a^b/2%c)%c here two part are same

///so you should return (a^b/2%c)^2 then %c.

}

else {

return ((a%c)*Exmod(a,b-1,c))%c;

}

 

 

}

int main()

{

int a,b,c,result;

scanf("%d%d%d",&a,&b,&c);

result = Exmod(a,b,c);

printf("result is : %d\n",result);

return 0;

}