UVa 10787 (Modular Equations) এর অ্যানালাইসিস

২০ শে জুলাই, ২০১৪ রাত ১১:৩৬

(প্রোগ্রামিং সংক্রান্ত বোরিং পোস্ট। Irrelevant পাঠকদের ঢুকার দরকার নেই )



প্রবলেমঃ UVa-10787



মডুলার অ্যারিথম্যাটিক এর একটি চমৎকার ব্যাবহার এখানে দেখা যাবে। প্রশ্নটা সংক্ষেপে এরকমঃ

তিনটি ইন্টিজার a (a_min ≤ a ≤ a_max), b (b_min ≤b ≤b_max) এবং m (m_min ≤m ≤m_max) দেয়া আছে। এরকম কয়টি ট্রিপল পাওয়া যাবে যেন (a+b) mod m = (a-b) mod m হয়?



এটা ব্রুট ফোর্স মেথডে করা যাবে না, কারণ a, b, m প্রত্যেকের মান ১০০০ টা। কাজেই কমপ্লেক্সিটি হবে O(1000*1000*1000) বা O(10^9)। কাজেই আমাদেরকে অন্য কোনও উপায় বের করতে হবে।

প্রশ্নে দেয়া ইকুয়েশনটা আবার দেখা যাকঃ

(a+b) % m = (a-b) % m

অর্থাৎ a এর সাথে এমন কিছু যোগ বা বিয়োগ করতে হবে যেন প্রাপ্ত সংখ্যাটাকে m দিয়ে ভাগ করলে একই ভাগশেষ পাওয়া যায়। মডুলার অ্যারিথমেটিক থেকে আমরা জানি, সংখ্যাটাকে অবশ্যই m এর গুনিতক হতে হবে। কয়েকটা উদাহরণ দিইঃ

17%5 = 2

17 এর সাথে 5 এর কোন গুণিতক যোগ বা বিয়োগ করলেও ভাগশেষ 2 পাওয়া যাবে। যেমনঃ

(17+5)%5 = 2

(17-5)%5 = 2

(17+15)%5 = 2

(17-15)%5 = 2

সুতরাং b এর মান হিসেবে আমাদেরকে m এর গুণিতক নিতে হবে। a এর মান যাই হোক, b_min থেকে b_max পর্যন্ত m-এর কয়টা গুণিতক আছে সেটা কাউন্ট করাই যথেষ্ট।



আবার m যদি জোড় সংখ্যা হয়, তাহলে আরেকটি ইন্টারেস্টিং ঘটনা ঘটে। যেমন (ধরি m = 6):

17 % 6 = 5

17-এর সাথে 6-এর গুণিতক যোগ/বিয়োগ করলেও ভাগশেষ 5 পাওয়া যাবে। 17-এর সাথে 3 (6/2) যোগ এবং বিয়োগ করলেও একই রকম ভাগশেষ পাওয়া যায় (যা আমাদের প্রবলেমের একটা সল্যুশন হিসেবে কাউন্ট করা যেতে পারে)।

(17+3) % 6 = 2

(17-3) % 6 = 2

কাজেই, m জোড় হলে আমাদেরকে m/2 এর গুণিতক কাউন্ট করতে হবে।

০ টি +০/-০