Codeforces Round #511 1034A, 1047C Enlarge GCD Solution

Problem:

n সংখ্যক নাম্বার দেয়া আছে । বলতে হবে- সর্বনিম্ন কয়টি সংখ্যা এই List থেকে Remove করলে, Remove করার আগে সবগুলো নাম্বার এর যে GCD, Remove করার পরে বাকি নাম্বার গুলোর GCD তার চেয়ে বড় হবে ?

Constraints:

• সর্বোচ্চ $3.10^5$ টা নাম্বার দেয়া থাকবে ।
• প্রতিটা নাম্বার এর সর্বোচ্চ মান হতে পারে 15000000 ($1.5 * 10^7$)

Here is the problem link...

Solution:

What is GCD?

GCD মানে হলো Greatest Common Divisor. GCD কে বাংলায় গরিষ্ঠ সাধারণ গুণনীয়ক বা গ.সা.গু. বলা হয় । দুই বা ততোধিক সংখ্যার GCD হলো- যেসব সংখ্যা দিয়ে প্রতিটি নাম্বারকেই নিঃশেষে ভাগ করা যায় ( অর্থাৎ, যেসব সংখ্যা দিয়ে প্রতিটা সংখ্যাকে ভাগ করলে কোন ভাগশেষ বা remainder থাকে না), এমন সংখ্যাগুলোর মাঝে সবচেয়ে বড় সংখ্যা ।

যেমন, ১২, ১৮ ও ৬০ এর GCD হলো.৬ । কারণ, যেসব সংখ্যা দিয়ে ১২,১৮ ও ৬০ প্রতিটি নাম্বারকেই নিঃশেষে ভাগ করা যায় তারা হলো- ১,২,৩,৬ । এদের মাঝে সবচেয়ে বড় হলো ৬ । তাই এদের GCD হলো ৬ ।

Relation of GCD with Prime Factors:

যেসব নাম্বার এর GCD বের করতে হবে, তাদের প্রতিটা নাম্বারকে যদি Prime Factorization (মৌলিক উৎপাদকে বিশ্লেষণ) করা হয়, তবে তাদের GCD হবে- যেসব Prime নাম্বার (মৌলিক সংখ্যা) প্রতিটা নাম্বার এর Divisor (উৎপাদক) হিসেবে আছে, তাদের প্রতিটি Prime নাম্বারকে দেখতে হবে কোন সংখ্যার মাঝে ঐ Prime কতবার গুণ আকারে আছে, অর্থাৎ কোন সংখ্যার মাঝে ঐ Prime এর Power বা ঘাত কত । প্রতিটা Prime এর জন্য ঐ Prime প্রদত্ত সংখ্যাগুলোর মাঝে সর্বনিম্ন যত বার আছে, অর্থাৎ Prime এর সর্বনিম্ন Power যত আছে, তত বার গুণ করতে হবে । এভাবে সব Prime কে গুণ করলে যে গুণফল পাওয়া যাবে সেটাই হলো ঐ সংখ্যাগুলোর GCD.

উদাহরণ:

মনে করি, আমরা ১২, ১৮ ও ৬০ এর GCD বের করব । এখন এদের প্রতিটাকে Prime Factorization(মৌলিক উৎপাদকে বিশ্লেষণ) করে পাই-

১২ = ২ * ২ * ৩
১৮ = ২ * ৩ * ৩
৬০ = ২ * ২ * ৩ * ৫

এখানে,  ২ ও ৩ এই দুইটা Prime প্রতিটা নাম্বার এর মাঝেই আছে ।
১২ এর মাঝে ২ আছে ২ বার, ১৮ এর মাঝে ২ আছে ১ বার, ৬০ এর মাঝে ২ আছে ২ বার । তাহলে ২ সর্বনিম্ন আছে ১ বার ।
১২ এর মাঝে ৩ আছে ১ বার, ১৮ এর মাঝে ৩ আছে ২ বার, ৬০ এর মাঝে ৩ আছে ১ বার । তাহলে ৩ সর্বনিম্ন আছে ১ বার ।

৫ শুধু ৬০ এর মাঝে আছে ১ বার, আর কারও মাঝে নেই । এজন্য ৫ নেয়া যাবে না ।

তাই ১২, ১৮ ও ৬০ GCD বের করার জন্য ২ গুণ হবে ১ বার, ৩ গুণ হবে ১ বার ।
সুতরাং, ১২, ১৮ ও ৬০ এর GCD = ২ * ৩ = ৬

Back to the Problem:

মনে করি, আমাদেরকে যে n টা নাম্বার দেয়া আছে, তাদের GCD হলো g.

তাহলে g এর Prime Factorization করলে যেসব Prime g এর মাঝে পাওয়া যাবে, তাদের প্রতিটা Prime g এর মাঝে যত বার আছে, n টা নাম্বার এর প্রতিটা নাম্বার এর মাঝে কমপক্ষে তত বার আছে, কিছু কিছু নাম্বার এর মাঝে তার চেয়েও বেশি বার আছে ।

আমাদেরকে n টা নাম্বার এর মাঝে সর্বনিম্ন পরিমাণ নাম্বারকে remove করে g এর মানকে আরো বড় বানাতে হবে । এখন, g এর মান আরো বড় করা হবে কিভাবে ? কিছু নাম্বারকে যদি লিস্ট থেকে বাদ দেয়া হয়, তবে g এর মান আরও বড় করা যেতে পারে । কী রকম ?

মনে করুন, আপনারা কিছু ফ্রেন্ড মিলে পিকনিকে যাবেন । এখন প্রত্যেকের চাদা কত করে ধরবেন ? প্রত্যেক ফ্রেন্ডকে আপনি জিজ্ঞেস করবেন যে সে সর্বোচ্চ কত চাদা দিতে পারবে । সব ফ্রেন্ড এর মাঝে যে সবচেয়ে কম পরিমাণ চাদা দিতে পারবে, আপনি যদি তার চেয়ে বেশি চাদা ধরেন, তবে সে যেতে পারবে না । তাহলে সর্বনিম্ন যত চাদা ধরলে প্রত্যেক ফ্রেন্ডই সেই পরিমাণ চাদা দিতে পারবে তত করে চাদা ধরবেন, তাই না?

এখন আপনার এই ফ্রেন্ডদের মাঝে কেউ অনেক কিপ্টে থাকতে পারে ( সেফু দার ভাষ্য মতে অনেক গরীব :p), যারা অনেক কম চাদা দিতে দিবে, বেশি হলে যাবে না পিকনিকে ।

কিন্তু আপনি দেখলেন এত কম চাদায় একটা জোস পিকনিক করা যাবে না । সো আপনি যেটা করতে পারেন তা হলো মাথা ব্যথা হলে মাথা কেটে ফেলার মত (বা ইউটিউবে বিতর্কিত ভিডিও আপলোড দিলে ইউটিউব বন্ধ করে দেয়া, বা ফেইসবুকে প্রশ্ন ফাস হলে ফেইসবুক বন্ধ করে দেবার মত :p) । যে বা যারা কম চাদা দেবে তাদের বাদ দিয়ে পিকনিকে যাবেন, যেহেতু বাকিরা বেশি করে চাদা দেবে তাই তাদের বাদ দিলে চাদার পরিমাণ বাড়ানো যাবে ।

আমাদের প্রোবলেমে কিন্তু বলেনি GCD কে maximize করতে হবে, অর্থাৎ, বাড়িয়ে যত বড় করা যায় তত বড় করতে হবে তা বলেনি ।

মানে, g এর মান এখন যা, নাম্বার remove করার পরে  তার চেয়ে বড় হলেই হলো । আমাদেরকে বলতে হবে, সর্বনিম্ন কয়টা নাম্বার remove করলে বাকি নাম্বারগুলোর GCD, g এর চেয়ে বড় হবে ।

GCD এর মান বড় করার জন্য আমরা কী করতে পারি ?

g এর মাঝে কোন একটা prime যত বার আছে, তাকে তার চেয়ে বেশি বার গুণ করলে g এর মান বাড়বে ।
কিছু prime g এর মাঝে নেই, তার মানে তারা 0 বার আছে মনে করতে পারি ।

g এর মান যেহেতু বড় করলেই হলো, তাহলে কোন একটা prime g এর মাঝে যত বার আছে, যদি তার চেয়েও একবার বেশি থাকার উপায় বের করা যায়, তবেই আমাদের কাজ শেষ !

ধরি, কোন একটা Prime p, g এর মাঝে আছে x বার । আমরা চাই, p কে x+1 বার রাখতে । p কখন x+1 বার থাকবে g এর মাঝে ? যদি প্রতিটা নাম্বার এর মাঝেই p কমপক্ষে x+1 বার থাকে, তবেই p g এর মাঝেও  x+1 বার থাকবে ।
তার মানে, এই লিস্টে যেসব নাম্বার এর মাঝে p কমপক্ষে x+1 বা তার চেয়ে বেশি বার আছে, তাদেরকে রেখে বাকি নাম্বারগুলোকে রিমুভ করতে হবে । ধরি, p কমপক্ষে x+1 বা তার চেয়ে বেশি বার আছে n টা নাম্বার এর মাঝে এমন আছে y টা । তাহলে রিমুভ করতে হবে n-y টা ।

তাহলে এভাবে প্রতিটা প্রাইম এর জন্য আমরা চেক করব যে ঐ প্রাইম এর পরিমাণ g এর prime factorization এ এক বাড়াতে কতগুলো নাম্বার রিমুভ করতে হবে । এভাবে যে ক্ষেত্রে সবচেয়ে কম পরিমাণ রিমুভ করতে হবে, সেই সর্বনিম্ন পরিমাণটাই হবে এই problem এর আউটপুট ।

Algorithm to solve the problem:

1. n টা নাম্বার এর GCD, g বের করি ।
2. n টা নাম্বার এর প্রতিটা নাম্বারকেই prime factorization করি ।
3. g এর মাঝে কোন prime কত বার আছে, তা বের করি ।
4. 1 থেকে 15000000 পর্যন্ত প্রতিটা prime নাম্বার এর জন্য সেই প্রাইম ১ বার আছে কতগুলো নাম্বার এর মাঝে, ২ বার আছে কতগুলো নাম্বার এর মাঝে, ৩ বার আছে কতগুলো নাম্বার এর মাঝে, .........বের করি ।
5. Cumulative sum (prefix sum) ব্যবহার করে 1 থেকে 15000000 পর্যন্ত প্রতিটা prime নাম্বার এর জন্য সেই প্রাইম ১ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, ২ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, ৩ বা তার বেশি বার আছে কতগুলো নাম্বার এর মাঝে, .........বের করি ।
6. প্রতিটা প্রাইম g এর মাঝে যত বার আছে, তার চেয়ে বেশি বার আছে কতগুলো নাম্বার এর মাঝে, তা বের করি । 
7. যদি কোন প্রাইম g এর মাঝে থাকে x বার, এবং প্রদত্ত n টা নাম্বার এর মাঝে যেসব নাম্বার এর মাঝে ঐ প্রাইম x+1 বা তার বেশি বার আছে এমন নাম্বার থাকে y টা, তবে রিমুভ করতে হবে n-y টা ।
8. যে প্রাইম এর জন্য n-y এর মান সর্বনিম্ন হয়, সেই n-y হবে আউটপুট ।

আজকের মত এই পোস্ট এখানেই শেষ । এই পোস্ট এর ২য় পর্বে implementation নিয়ে আলোচনা করব । ২য় পর্বে আরো থাকবে, আরো বিকল্প কী কী উপায়ে এই প্রোবলেম সলভ করা যায়, কিভাবে এই সলিউশনকে টাইম ও মেমোরি ইফিসিয়েন্ট করা যায় । ফাইনালি থাকবে এই প্রোবলেম এর জন্য আমার accepted সলিউশন ও সলিউশন এর বিভিন্ন অংশের ব্যাখ্যা ।

আমি রিকমেন্ড করব, প্রথমে আপনি সর্বোচ্চ চেস্টা করুন, নিজে ইমপ্লিমেন্ট করতে । না পারলে অপেক্ষা করুন ২য় পর্বের জন্য ।

পোস্টের কোন অংশে বুঝতে সমস্যা হলে বা কোন ভুল চোখে পড়লে, কমেন্ট করুন । 

আমার ব্লগ বা পোস্ট নিয়ে কোন পরামর্শ বা কোন বিষয়ে আপনি পোস্ট চান তা কমেন্টে বলুন । আমি চেস্টা করব সেই বিষয়ে পোস্ট দিতে ।

হ্যাপি কোডিং । আল্লাহ হাফেজ ।।

এই পোস্টের ২য় পর্ব