UVa 10791 - Minimum Sum LCM

প্রবলেম লিঙ্ক : https://goo.gl/9xPtfS

তোমাকে একটি সংখ্যা N দেওয়া থাকবে। কমপক্ষে এমন দুইটি সংখ্যার যোগফল বের করতে হবে যাদের ল.সা.গু হবে N এবং যোগফলটি হবে সর্বনিম্ন। ল.সা.গু বের করার একটি পদ্ধতি হতে পারে Prime Factorization. আমরা এখানে N-এর Prime Factorization করতে পারি। প্রতিটি প্রাইমের জন্য তাদের সর্বোচ্চ পাওয়ারের যোগফলই হবে আমাদের কাঙ্ক্ষিত আউটপুট। কিন্তু আমাদের আবার ক্রিটিকাল কেইস নিয়েও ভাবতে হবে। যদি N-এর মান 1 হয়, কিংবা N একটি প্রাইম হয় কিংবা N-এর মাত্র একটিই প্রাইম ফ্যাক্টর থাকে, তবে আউটপুট হবে N+1.

আমরা এবার কিছু উদাহরণ দেখি। 😀

N যখন 1 : 1 = 1 * 1; এক্ষেত্রে আমরা 1+1 = 2-ই পাবো। কারণ, এই এক জোড়া 1 বাদে 1-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না।

N যখন প্রাইম : 2 = 1 * 2, 3 = 1 * 3, 5 = 1 * 5; এক্ষেত্রেও আমরা N+1-ই পাবো। কারণ, 1 আর N বাদে N-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না।

N-এর প্রাইম ফ্যাক্টর যখন মাত্র একটিই : 4 = 2 * 2, 27 = 3 * 3 * 3, 64 = 2 * 2 * 2 * 2 * 2 * 2, 81 = 3 * 3 * 3 * 3; এসব ক্ষেত্রেও N-এর 1 আর N বাদে N-এর আর কোন একাধিক সংখ্যার ল.সা.গু হওয়া সম্ভব না। কারণ, এক্ষেত্রে প্রাইমই আছে একটি। আমরা যদি ওই প্রাইমটির সর্বোচ্চ পাওয়ার বের করি তবে সেটা শেষমেশ N-ই হবে। 😛 কিন্তু আমার তো শুধু N দিয়েই কাজ হচ্ছে না, কারণ মিনিমাম দুইটা সংখ্যা লাগবে।  আমরা জানি, 1 আর N-এর ল.সা.গু সবসময়ই N. তাই আমরা এখানেও চোখ বন্ধ করে বলে দিতে পারি, আউটপুট হবে N+1.

যখন N একটি নিরীহ শান্তশিষ্ট সংখ্যা  : আমরা এইসব কেইসের জন্য N-এর Prime Factorization করব। তারপর N-এর প্রাইম ফ্যাক্টরগুলোর পাওয়ার নিয়ে যোগ করতে থাকব এবং যোগফলটাই হলো আউটপুট। এখানে সর্বোচ্চ পাওয়ারের কথা কেন বলা হলো এবার আমরা নিচের উদাহরণের মাধ্যমে দেখি। 😊

ধরা যাক, আমাকে 4, 6 আর 12-এর ল.সা.গু বের করতে হবে। আমরা প্রতিটাকে Prime Factorize করি। 

4 = 2^2

6 = 2 * 3

12 = 2^2 * 3

দেখা যাচ্ছে, এখানে প্রাইম ফ্যাক্টরগুলো হলো, 2 আর 3; 2-এর সর্বোচ্চ পাওয়ার হলো 2 আর 3-এর সর্বোচ্চ পাওয়ার হলো 1. তাহলে আমরা ল.সা.গু পাই, 2^2 * 3^1 = 12 আর পাওয়ারগুলো যোগ করে পাই, 2^2 + 3 = 7.

এখন 7-ই যে আমাদের সর্বনিম্ন যোগফল তা বুঝতে আমরা আরেকটু সামনে এগোই।

12 এর ফ্যাক্টরগুলো হচ্ছে -> 1, 2, 3, 4, 6, 12.
আবার, 12 = 1 * 12 = 2 * 6 = 3 * 4.

সর্বনিম্ন যোগফলের জন্য আমার এখানে দুইটা সংখ্যা  নিলেই হচ্ছে। এর বেশি নিলে সর্বনিম্ন যোগফল পাওয়া যাবে না।
দুইটি সংখ্যার জন্য, আমরা পাই, 12 = 1 * 12 = 3 * 4
এখানে, 1+12 > 4+3  
বা, 13 > 7.
সুতরাং, 12 এর জন্য আউটপুট হবে 7. 😊

এই ছিল UVa 10791 - Minimum Sum LCM এর সল্যুশন হিন্ট। বুঝতে সমস্যা হলে কমেন্ট করতে ভুল করো না। 😊