Modular and Big Modular

মডুলার সম্পর্কে আমরা সবাই কম-বেশি জানি তবে মোটে না জানলেও সমস্যা নেই এটা খুব সহজ একটা বিষয় ।

modular

5%2=1

6%4=2

13%5=3

কিছু কি বোঝা যায় ? আসলে বিষয় হল, শেষ উদাহরণের জন্য বলি, 13 থেকে ছোট 5 এর সর্বচ্চ multiple হল 10 সুতরাং   13 mod 5 = (13-10) = 3. এখন তোমার (c/c++) compiler-এ 13%5 এবং -13%5 বের কর, দেখবে 3 এবং -3 উত্তর আসছে ।  প্রথম উত্তরটা ঠিক থাকলেও দ্বিতীয়টা ভুল, আসলে এখানে reminder বের করা হয়ছে ।

এখন দেখা যাক -13%5=? 

-13 এর থেকে ছোট 5 এর সর্বচ্চ multiple হল -15, সুতরাং -13%5 = (-13-(-15)) = -13+15 = 2 .

online judge এ মডুলো বের করার কোন সমস্যা সমাধানের সময় এই case টা মাথায় রাখা খুব জরুরী । তাহলে কিভাবে এই code টা করা যেতে পারে ? যে সংখ্যা দ্বারা mod করা হচ্ছে সেই সংখ্যার সাথে negative উত্তরটা যোগ করে দাও, হয়ে গেল ! না বুঝলে code টা দেখ, এটা negative, positive সব সংখ্যার জন্য ।

#include<bits/stdc++.h> using namespace std; int main() { long long m, n, r; while(cin>>m>>n){ r=m%n; if(r<0) r=r+n; cout<<r<<endl; } return 0; }

     100! %103=? এইটা পারবে ?

যদি 100! বের করে 103 দ্বারা মডুলো করতে চাও সেটা অসম্ভব । 100! এর কথা একটু চিন্তা করে দেখ ।

তবে আমরা জানি,       100!=(100*99*98*.......................3*2*1) 

দুইটা সুত্র দেখ 

                            1.  (a+b)%m = ((a%m)+(b%m))%m

                            2. (a*b)%m = ((a%m)*(b%m))%m

এখন দ্বিতীয় সুত্রটা ব্যবহার করে সমাধান করতে পারবে ।

আমাকে যদি বলে 12345678912345678912345678912 % 7 = ?

লক্ষ্য কর এখানে সংখ্যাটা 30 digit-এর । সাধারণত long long এ 19 digit পর্যান্ত নেয় unsigned long long নিলে সেখনে 20 digit পর্যান্ত calculate করবে । তাহলে কিভাবে 30-40 digit বা তার থেকে বেশি digit এর সংখ্যার মডুলো বের করতে পারি ?

 এখানে আমাদের string এর সাহায্য নিতে হবে কেননা string-এ 30-40 digit একটা মামুলি ব্যাপার। তবে এক্ষেত্রে দুইটা বিষয়ে ধারণা থাকতে হবে 

1.  321 = (((3*10)+2)*10)+1

            = ((30+2)*10)+1

            = (32*10)+1

            = 320+1

            =321

2. কোন digit এর character মান থেকে  integer মানে নিয়ে আসতে 48 বিয়োগ করতে হয় ।

এখন নিচের code-টা দেখ 

#include<bits/stdc++.h> using namespace std; int main() { int s=0, n, m, x, i; string a; cin>>a; cin>>m; n=a.size(); for(i=0; i<n; i++){ x=a[i]-48; s=(s*10+x)%m; } cout<<s<<endl; return 0; }

Modulo of Big Number

#include<bits/stdc++.h> using namespace std; int main() { int s=0, n, m, x, i; string a; cin>>a; cin>>m; n=a.size(); for(i=0; i<n; i++){ x=a[i]-48; s=(s*10+x)%m; } cout<<s<<endl; return 0; }

UVa 374-Big Mod

3 4

#include<bits/stdc++.h> using namespace std; long long m, a, b; long long bigmod(long long b) { if(b==0) return 1; else if(b%2==1) return (bigmod(b/2)*a*bigmod(b/2))%m; else return (bigmod(b/2)*bigmod(b/2))%m; } int main() { while(scanf("%lld%lld%lld", &a,&b,&m)!=EOF) cout<<bigmod(b)<<endl; return 0; }