Chinese Remainder Theorem

ধরা যাক, আমাদের এমন একটা সংখ্যা X বের করতে বললো যাকে কিনাঃ

- ২ দিয়ে ভাগ করলে ভাগশেষ ১ থাকে

- ৩ দিয়ে ভাগ করলে ভাগশেষ ২ থাকে

- ৭ দিয়ে ভাগ করলে ভাগশেষ ৫ থাকে

এই ধরনের প্রবলেম গুলো "Chinese remainder theorem" ব্যবহার করে খুব সহজেই সমাধান করা যায়, তবে একটা শর্ত হচ্ছে যেই সংখ্যা গুলো দিয়ে ভাগ করা হবে সেগুলো relatively prime হতে হবে। মানে যেকোন ২ টি সংখ্যার GCD (Greatest Common Divisor) সবসময় ১ হবে। উপরে উল্লেখিত সমস্যায় ২,৩,৭ সংখ্যা ৩ টি relatively prime. অর্থাৎ এই সমস্যাটিকে CRT দিয়ে সমাধান করা সম্ভব।

Chinese remainder theorem এমন একটি সংখ্যা X বের করে, যেখানে X হচ্ছে –

X ≡ C1 (mod P1)

X ≡ C2 (mod P2)

X ≡ C3 (mod P3)

.

.

X ≡ Cn (mod Pn)

কোন প্রবলেমকে এইরকম অনেকগুলো linear congruence* এর ইকুশেনের একটি সিস্টেম আকার সাজানো গেলে, চাইনিজ রিমাইন্ডার থিওরাম অনুযায়ী X বের করার জন্য নিজের সমীকরণ ব্যবহার করা হয়ঃ

X = B1*X1*C1 + B2*X2*C2 + B3*X3*C3 + …… + Bn*Xn*Cn

এখানে,

Bi = B / Pi   [ i = 1, 2, 3,,,, n ]

B = P1 * P2 * P3 * … * Pn

B1, B2,,, Bn এবং C1, C2,,,,,Cn এর মান প্রবলেমে উল্লেখ করা থাকবে।  

X1, X2,,, Xn এর মান বের করার জন্য নিচের সমীকরণটি ব্যবহার করা হয়,যা সকল Bi, Xi এবং Pi এর জন্য সত্য,

          Bi*Xi ≡ 1 (mod Pi)   [ i = 1, 2, 3,,,,,n ]

এখন, যেহেতু Bi এবং Pi relatively prime সেহেতুঃ

          Bi*x + Pi*y = 1

এইখানে, x = Xi এবং y যে কোন একটি সংখ্যা।

উপরের সমীকরণটি (Bi*x + Pi*y = 1) Extended Euclid Algorithm এর মাধ্যমে সমাধান করলেই আমরা Xi এর মানে পেয়ে যাব।

X এর মান বের করার পর নিচের সমীকরণ ব্যবহার করে X এর অসংখ্য মান বের করা সম্ভব,

          X = X ± i*B        [ i = 1, 2, 3. . . . . . ]

আমরা এখন ব্লগের শুরুতে উল্লেখিত সমস্যাটিকে চাইনিজ রিমাইন্ডার থিওরামের মাধ্যমে সমাধান করবো। সমস্যাটিকে ৩ টি linear congruence* ইকুয়েশনের একটা সিস্টেম হিসেবে দেখানো যায় নিম্নোক্ত ভাবেঃ

X ≡ 1 (mod 2)

X ≡ 2 (mod 3)

X ≡ 5 (mod 7)

এখানে, P1 = 2, P2 = 3, P3 = 7 এবং C1 = 1, C2 = 2, C3 = 5

এখন, 'Chinese remainder theorem' অনুযায়ী,

X = B1*X1*1 + B2*X2*2 + B3*X3*5

এখানে,

B = B1 * B2 * B3 = 2 * 3 * 7 = 42

তাহলে,

B1 = 42 / 2 = 21

B2 = 42 / 3 = 14

B3 = 42 / 7 = 6

সুতরাং,   X = 21*X1*1 + 14*X2*2 + 6*X3*5

এখন,

B1*X1 ≡ 1 (mod P1) => 21 * X1 ≡ 1 (mod 2) => 21 * X1 + 2 * y = 1

B2*X2 ≡ 1 (mod P2) => 14 * X2 ≡ 1 (mod 3) => 14 * X2 + 3 * y = 1

B3*X3 ≡ 1 (mod P3) => 6 * X3 ≡ 1 (mod 7) => 6 * X3 + 7 * y = 1

উপরের 3 টি সমীকরণকে, Extended Euclid Algorithm দিয়ে সমাধান করে পাই,

X1 = 1, X2 = -1 এবং X3 = -1

সুতরাং,

X =  21*1*1+ 14*(-1)*2 + 6*(-1)*5

    = 21 – 28 – 30

    = -37

অর্থাৎ -37 হচ্ছে এই সমস্যাটির অনেকগুলো সমাধান এর একটি J
X = X ± i*B, সমীকরণটি ব্যবহার করে আরো অসংখ্য সমাধান বের করা যাবে।

Chinese Remainder Theorem ব্যবহার করে আলোর 1319 প্রবলেমটা সল্ভ করা যাবে।

*Linear congruence : এই লিঙ্কে Linear congruence ইকুয়েশন সম্পর্কে জানা যাবে।

Find the sum of divisors from 1 to n

ধরা যাক, আপনাকে একটা সংখ্যা n দিয়ে বললো 1 থেকে n পর্যন্ত সংখ্যাগুলোর divisor(1 এবং সেই সংখ্যা বাদে) গুলোর যোগফল বের করতে।

যেমনঃ 6 এর divisor গুলো হচ্ছে 2, 3। যোগফল হচ্ছে 5।

এখন n এর মান যদি 6 হয় তাহলে উত্তর হবে 0+0+0+2+0+5 = 7। যেহেতু 1, 2, 3, 4, 5 ,6 সংখ্যাগুলোর divisor গুলোর যোগফল যথাক্রমে 0, 0, 0, 2, 0, 5।

O(n) solution:

এই প্রবলেমটার সবচেয়ে সহজ সমাধান হচ্ছে 1 থেকে n পর্যন্ত একটা for লুপ চালিয়ে প্রত্যেকটি i এর জন্য (floor(n / i) – 1) * i বের করে যোগ করা। এইখানে floor(n/i) এর মাধ্যমে বের করা হচ্ছে 1 থেকে n পর্যন্ত কতগুলো সংখ্যা i দিয়ে divisible.

যেমনঃ 6/2 = 3, এর মানে হচ্ছে 1 থেকে 6 পর্যন্ত 3 টি সংখ্যা (2, 4, 6) 2 দিয়ে divisible.

আর floor(n/i) থেকে 1 বিয়োগ করা হচ্ছে কারণ divisor হিসেবে নিজেকে নেয়া যাবে না। অর্থাৎ এখানে 6 এর divisor হচ্ছে শুধু 2 এবং 3।

O(n/2) solution:

উপরের সলুশনের ক্ষেত্রে আসলে n/2 পর্যন্ত ফর লুপ চালালেই আমরা সলুশন পেয়ে যাব কারণ n/2+1 থেকে n পর্যন্ত সংখ্যা গুলো নিজেদের ছাড়া 1 থেকে n পর্যন্ত অন্য কোন সংখ্যার-ই divisor না।

O(sqrt(n)) solution:

আমরা আগেই দেখেছি, যদি floor(n/i) = x হয় এর মানে হচ্ছে 1 থেকে n পর্যন্ত নিজেকে ছাড়া x-1 টি সংখ্যা i দ্বারা divisible. উল্টাটাও কিন্তু সত্য, মানে হচ্ছে 1 থেকে n পর্যন্ত নিজেকে ছাড়া i-1 টি সংখ্যা x দ্বারা divisible.

ধরা যাক, n = 30। 1 থেকে 30 পর্যন্তু সংখ্যাগুলোর divisor (1 এবং নিজেকে বাদে) গুলো নিচে দেয়া হলঃ

1 –                                                                       

2 –                                                          

3 –                                                                       

4 – 2                                                               

5 –                                                                

6 – 2, 3                                                        

7 –                                                                        

8 – 2, 4                                                  

9 – 3                                                                     

10 – 2, 5  
11 --           
12 – 2, 3, 4, 6   
13 --             
14 – 2, 7
15 – 3, 5   
16 – 2, 4, 8
17 -- 
18 – 2, 3, 6, 9  
19 -- 
20 – 2, 4, 5, 10    
21 – 3, 7          
22 – 2, 11         
23 --
24 – 2, 4, 6, 12
25 -- 5
26 – 2, 13
27 – 3, 9
28 – 2, 4, 7, 14
29 --
30 – 2, 3, 5, 6, 10, 15

floor(30/2) = 15, অর্থাৎ 1 থেকে 30 পর্যন্ত 2 টি সংখ্যা 15 দ্বারা divisible, নিজেকে বাদ দিলে 1 শুধু একটি সংখ্যা(20) 15 দ্বারা divisible।

আবার floor(30/3) = 10, অর্থাৎ 1 থেকে 30 পর্যন্ত নিজেকে বাদে 2 টি সংখ্যা (20, 30) 10 দ্বারা divisible।

এখন একটূ খেয়াল করলে দেখা যাবে যে, floor(30/3)+1 = 11 থেকে floor(30/2) = 15 পর্যন্ত 5 টি সংখ্যার (11, 12, 13, 14, 15) প্রত্যেকটি 1 থেকে 30 পর্যন্ত 2 টি সংখ্যার divisible। 

একইভাবে floor(30/4)+1 = 8 থেকে floor(30/3) = 10 পর্যন্ত 3 টি সংখ্যার (8, 9, 10) প্রত্যেকটি 1 থেকে 30 পর্যন্ত 3 টি সংখ্যার divisible।

অর্থাৎ, floor(n/i) + 1 থেকে floor(n/(i+1)) পর্যন্ত সংখ্যাগুলোর প্রত্যেকটি 1 থেকে n পর্যন্ত i টি সংখ্যার divisible।

তাহলে, আমরা আসলে 1 থেকে sqrt(n) পর্যন্ত ফর লুপ চালালেই সলুশন পেয়ে যাচ্ছি।

Code:                   

for(i=2; i <= sqrt(n); i++) {
 ans = ((n/i) - 1) * i;
 
 temp = n / i;
 if(temp > i) {
  a = n / (i+1);
  b = n / i;
  sum1 = (a * (a+1)) / 2;
  sum2 = (b * (b+1)) / 2;

  ans += (sum2 - sum1) * (i - 1);
 }
 
}

এই ব্লগটা খুবই তাড়াহুড়ো করে লিখা, তাই ঠিকমত সবকিছু গুছায়ে বলা হয় নাই। তাছাড়া এইটাই আমার ফার্স্ট ব্লগ, তাই পড়ে কিছু না বুজলে আমার কিছু করার নাই :p ।  আর যদি বুজতে পারলে আলোর (lightoj.com) 1098 নাম্বার প্রবলেমটা সল্ভ করা যেতে পারে, কোড তো দিয়াই দিলাম :p ।

তবে আশা করি, সামনে আরো সুন্দর করে সময় নিয়ে নিয়মিত ব্লগ লিখব :D