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 এর সল্যুশন হিন্ট। বুঝতে সমস্যা হলে কমেন্ট করতে ভুল করো না। 😊

ফ্যাক্টোরিয়ালের ভেতরের পোকা

তোমাদের সেই ছোট্ট ছেলে পিনোকিওর কথা মনে আছে ??? যে কিনা একটি গ্রামে বাস করত আর মিথ্যে কথা বললেই যার নাক হয়ে যেত ইয়া লম্বা!

তো সেই পিনোকিও একদিন দুপুরবেলা ঘুরতে বেরোলো, কোথায় যাবে তার ঠিক নেই। মা নিষেধ করলেন বের হতে। কিন্তু পিনোকিও ঘুরতে যাবেই। তো যেতে যেতে সে অনেকদূর চলে এসেছে। সামনে পড়ল এক ঝর্ণা। এদিকে হাঁটতে হাঁটতে পিনোকিও বেশ ক্লান্ত। ঝর্ণার মিষ্টি পানি খেয়ে যেইনা একটু জিরোনোর জন্য বসেছে, অমনি যেন কোথা থেকে চার শিংয়ের এক গুঁফোদৈত্য এসে হাজির। দৈত্য বললো, এই ঝর্ণার পানি সে কাউকে ছুঁতেও দেয় না। কিন্তু আজ দুপুরে সে উদরপূর্তি করে ভাতঘুম দিতে গিয়েছিল। তাই পিনোকিও কোন দিক থেকে এসে পানি খেয়ে নিয়েছে সেটা সে বুঝতেই পারেনি। এখন ঘুম ভেঙ্গে দৈত্য তো বেজায় রাগ করে বসে আছে। আর পিনোকিওকে একটা শাস্তি দেওয়ার প্ল্যান করছে মনে মনে। বেচারা পিনোকিও ভাবছে, " ইশশ, কেনো যে মায়ের কথা অমান্য করে এখানে এলাম??? 😭"

গুঁফো বললো, সে গণিত খুউব্বই ভালোবাসে। তাকে একটা সংখ্যা দেওয়া হলে, সে চটপট ওইটার ফ্যাক্টোরিয়াল বের করে দিতে পারে। কিন্তু সংখ্যাটা আবার 20 এর বেশি হতে পারবে না! 😛

কিন্তু সে কয়েকদিন ধরে একটা সমস্যা সমাধান করতে চেষ্টা করছে। সে একটি সংখ্যার ফ্যাক্টোরিয়ালে অন্য আরেকটি সংখ্যা ঠিক কতবার আছে সেটা বের করতে চাচ্ছে। গুঁফোদৈত্য অনেক চেষ্টা করেও তার কোন সমাধানে আসতে পারছে না। তো পিনোকিওকে সেটা্র সমাধান দিতে হবে।

যারা "ঠিক কতবার আছে" এই কথাটা বুঝতে পারোনি, তারা একটা বিষয় লক্ষ্য করো, দৈত্য আসলে প্রথম সংখ্যার ফ্যাক্টোরিয়ালে দ্বিতীয় সংখ্যা কতবার আছে সেটা বের করতে চেয়ে আসলে তার সর্বোচ্চ পাওয়ার কত সেটাই বের করতে বলেছে। 

পিনোকিও এটা শুনে তো খুব ভয় পেয়ে গেলো। কারণ দৈত্যের সমাধান করতে হলে তো এখন তাকে ফ্যাক্টোরিয়াল বের করে দিতে হবে, তারপর তাকে গুণে গুণে হিসাব করতে হবে ওই পিচ্চি সংখ্যাটা ঠিক কতবার আছে ফ্যাক্টোরিয়ালের ভেতর! 😩

সে আসলো তোমার কাছে। কারণ তুমি আবার কনটেস্ট-ফনটেস্ট না কি একটা করো। তাই তোমার কাছে এসব তো ডালভাত। তুমিও মহানন্দে লেগে গেলা পিনোকিওকে সাহায্য করতে, নাহলে দৈত্য যে তাকে ছাড়বে না বাপু।

পিনোকিও একটা সংখ্যার প্রাইম ফ্যাক্টরগুলো বের করতে জানে। সে জানে যেকোন সংখ্যাকেই কতগুলি প্রাইম নাম্বারের পাওয়ারের গুণফল আকারে লিখা যায়। যেমন, আমরা চাচ্ছি, ১০কে প্রাইম ণাম্বারে ভাঙ্গাবো, আমরা তখন লিখব,

10 = 2^1 * 5^1

একইভাবে, 20 = 2^2 * 5^1
100 = 2^2 * 5^2

তো দেখা যাচ্ছে, আমরা একটি সংখ্যার প্রাইম ফ্যাক্টোরাইজেশন করতে হলে প্রথমে 2 থেকে শুরু করবো, যতক্ষণ 2 দ্বারা ভাগ করা যাচ্ছে ভাগ করতেই থাকব। একটা সময় আর 2 দ্বারা ভাগ করা না গেলে, তখন আমরা দেখবো সেটাকে 3 দ্বারা ভাগ করা যায় কিনা। তারপর 5, 7, 11, 13, 17, 19 ইত্যাদি ইত্যাদি।

এখন কথা হলো, ফ্যাক্টোরিয়ালে আরেকটা সংখ্যা কতবার থাকবে তার সাথে আবার এই প্রাইম ফ্যাক্টোরাইজেশনের সম্পর্ক কী? আছে, বলছি। 😋

আপাতত আমরা গুঁফোর সমস্যায় ফিরে যাই। খুব আশ্চর্যজনক হলেও সত্য যে, এই পাওয়ার বের করতে হলে আমাদের কোন ফ্যাক্টোরিয়ালই বের করা লাগবে না। আমাদের গুঁফোদৈত্যের সমাধান দিতে হলে আগে যে ব্যাপারটা মাথায় রাখা লাগবে তা হলো, যে সংখ্যাটি ফ্যাক্টোরিয়ালে কতবার আছে তা বের করতে বলা হয়েছে সেটি কি প্রাইম নাকি কম্পোজিট।

যদি প্রাইম হয়

সেটা আমরা খুব সহজেই বের করতে পারবো ফরাসী গণিতবিদ Legendre'র একটি চমৎকার সূত্র দিয়ে। তাঁর সূত্রমতে, একটি সংখ্যা n এর ফ্যাক্টোরিয়ালে আরেকটি প্রাইম p এর সর্বোচ্চ পাওয়ার কত হবে, সেটা বের করতে হলে আমরা শূন্য না হওয়া পর্যন্ত n-কে p দিয়ে ভাগ করতেই থাকব, করতেই থাকব। আর প্রতিবার ভাগফলগুলোর পূর্ণসাংখ্যিক মান নিয়ে যোগ করতে থাকব। এভাবে ভাগ করতে থাকলে এক সময় আমাদের n-এর মান শূন্য হবে, এভাবে যোগফলটাই হবে আমাদের সর্বোচ্চ পাওয়ার, hurrah !! 😄

একটা ছোট্ট উদাহরণ দিয়ে ব্যাখ্যা করা যাক।

ধরো, আমরা ১০ এর ফ্যাক্টোরিয়ালে ২ কতবার আছে সেটা বের করব। এখন আমরা এর ধাপগুলো দেখি।

ধাপ 1 : 10/2 = 5.0; আমরা নিবো 5. যোগফল = 5.
ধাপ 2 : 5/2 = 2.5; আমরা নিবো 2. যোগফল = 5+2 = 7.
ধাপ 3 : 2/2 = 1.0; আমরা নিবো 1. যোগফল = 7+1 = 8.
ধাপ 4 : 1/2 = 0.5; এখানে আমাদের থামতে হবে কারণ ভাজ্য 1, 2 এর চেয়ে ছোট, তাই ভাগফলের পূর্ণসাংখ্যিক মান হবে 0।

তো আমরা পেলাম, 10! এ 2 আছে 8 বার। গাণিতিকভাবে, 10! = 3628800 আর 2^8 = 256. আমরা 10! কে 2^8 দ্বারা ভাগ করলে 14175 পাবো, যেটাকে আর 2 দ্বারা ভাগ করা যাচ্ছে না।

যদি কম্পোজিট হয়

এটা বের করাও খুব একটা কঠিন না। আমরা প্রথমে প্রাইম ফ্যাক্টোরাইজেশন দেখেছি, এক্ষেত্রে আমরা নিচের ধাপগুলো অনুসরণ করব।

ধাপ 1 : যে সংখ্যাটার পাওয়ার বের করতে বলবে সেই সংখ্যাটাকে আগে প্রাইম ফ্যাক্টরাইজ করবো। ধরে নেই, আমাকে 100! এর ভেতর 18 কতবার আছে সেটা বের করতে বলা হয়েছে। তো আগে আমরা 18 এর প্রাইম ফ্যাক্টোরাইজেশন করব এভাবে, 18 = 2 * 3^2.

ধাপ 2 : এবার প্রতিটি প্রাইম ফ্যাক্টর দিয়ে প্রথম সংখ্যাটাকে আগের সূত্রের মতোই ভাগ করতে থাকব। এভাবে ভাগ করলে আমরা 2 এর জন্য পাওয়ার পাবো 97 এবং 3 এর জন্য পাওয়ার পাবো 48.

ধাপ 3 : এবার প্রতি প্রাইমের পাওয়ারকে ওই প্রাইমের ফ্রিকোয়েন্সি দিয়ে ভাগ করবো। লক্ষ্য করলে দেখা যাবে যে, 18 এর প্রাইম ফ্যাক্টোরাইজেশনে 2 আছে 1 বার, তাই 2 এর ফ্রিকোয়েন্সি 1. একইভাবে 3 এর ফ্রিকোয়েন্সি হচ্ছে 2. আমরা ভাগ করলে 2 এর জন্য পাবো, 97/1 = 97 এবং 3 এর জন্য পাবো 48/2 = 24.

ধাপ 4 : সবশেষে আমরা সবগুলো ভাগফলের সর্বনিম্ন মানটা নিব। 97 এবং 24 এর মধ্যে সর্বনিম্ন হচ্ছে 24. সুতরাং, আমাদের সর্বোচ্চ পাওয়ার হবে 24.

আর এভাবেই পিনোকিও গুঁফোদৈত্যের সমস্যার সমাধান করে ফেলেছিলো। এখন সে তোমার কাছে আরেকটি আবদার নিয়ে এসেছে যে তাকে কিছু প্রোগ্রামিং সমস্যা দিতে হবে যেগুলো করে সে বেশ ভালভাবেই ব্যাপারটা আয়ত্ত্বে আনতে পারবে। গুঁফোদৈত্য তো 20 এর বেশি ফ্যাক্টোরিয়াল চিন্তা করতেই পারতো না, এখন পিনোকিও 20 এর চেয়ে অনেক বড় সংখ্যার ফ্যাক্টোরিয়ালের জন্যও এই হিসাব-নিকাশ করতে পারবে। আর সে এটাও বুঝতে পেরেছে যে, কখনো বড়দের কথার অবাধ্য হতে হয়না। 😊

রিলেটেড প্রবলেম :

1. UVa 10780 - Again Prime? No Time.
2. UVa 10139 - Factovisors
3. SPOJ BDOI16B - Beautiful Factorial Game

রেফারেন্স লিংক :

• https://goo.gl/zWKVrJ

হ্যাপী কোডিং। 😂

হ্যাপী নাম্বার থিওরিং! 😉