Codeforces Round #511 1034A, 1047C Enlarge GCD Solution [Part 2]

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

গত পর্বে যে সলিউশন বলেছিলাম, তা ছিল সবগুলো নাম্বার এর GCD বের করা ও প্রতিটা নাম্বার এর Prime Factorization করা । এরপরে GCD এর ভ্যালু তে যে প্রাইম যত বার আছে, ঐ প্রাইম কতগুলো নাম্বারে তার চেয়ে বেশি বার আছে সেটা বের করা এবং বাকি নাম্বারগুলোকে রিমুভ করা ।

Prime Factorization in Efficient way:

এখন Prime Factorization এর সাধারণ যে পদ্ধতি সবাই ব্যবহার করে, তার কমপ্লেক্সিটি- $O(sqrt(n))$ ।

এই প্রোবলেমে $3*10^5$ টা নাম্বার আছে, প্রতিটা নাম্বার হতে পারে সর্বোচ্চ $1.5 * 10^7$ । তাই $O(sqrt(n))$  কমপ্লেক্সিটিতে Prime Factorization করলে টাইম লিমিটে কুলাবে না ।

এজন্য আমাদেরকে $O(logn)$ কমপ্লেক্সিটিতে Prime Factorization করতে হবে । এ জন্য আমরা প্রথমে সিভ চালিয়ে প্রতিটা নাম্বার এর সর্বনিম্ন প্রাইম ফ্যাকটর বের করে নেব ।

 এখন কোন নাম্বার এর Prime Factorization এর সময় সেই নাম্বার এর সর্বনিম্ন প্রাইম ফ্যাকটর দিয়ে যতক্ষণ ভাগ করা যায়, ভাগ করতে থাকব । ভাগ করার পরে যে নতুন নাম্বার পাব, তাকেও আবার তার সর্বনিম্ন প্রাইম ফ্যাকটর দিয়ে যতক্ষণ ভাগ করা যায়, ভাগ করতে থাকব । এভাবে যতক্ষণ সংখ্যাটি ১ এর চেয়ে বড় ততক্ষণ চলতে থাকবে ।

তাহলে GCD এর Prime Factorization এ কোন প্রাইম কত বার আছে, সেটা বের করার জন্য কোড হবে এরকম-

যেহেতু কোন নাম্বার এর সর্বোচ্চ log(n) টা প্রাইম ফ্যাকটর থাকতে পারে, তাই এটার কমপ্লেক্সিটি হবে $O(logn)$

Using Memory in Efficient Way:

এখন প্রতিটা প্রাইম ১ বার আছে কতগুলো নাম্বারে, ২ বার আছে কতগুলো নাম্বারে,... এভাবে সর্বোচ্চ ২৩ বার আছে কতগুলো নাম্বারে তা স্টোর করতে একটা 2D অ্যারে freq[][] লাগবে, যেখানে freq[i][j] স্টোর করবে i তম প্রাইম j বার আছে অ্যারের কতগুলো নাম্বারে । এই অ্যারের সাইজ হবে $1.5 * 10^7 * 24$ । কিন্ত এত বড় অ্যারে মেমোরি লিমিটে কুলাবে না । তাহলে কী করতে পারি ?

1.5 * 10^7 পর্যন্ত প্রাইম আছে 970704 টা । আমরা প্রাইম নাম্বার ইউজ না করে তার সিরিয়াল নাম্বার ব্যবহার করতে পারি । ১ম প্রাইম ২, ২য় প্রাইম ৩, ৩য় প্রাইম ৫,... । তাই ২ এর জন্য ১, ৩ এর জন্য ২, ৫ এর জন্য ৩,... ব্যবহার করব । তাহলে এই 2D অ্যারের সাইজ হবে 970704 * 24, যা মেমোরি লিমিটে কুলাবে ।

Calculating Frequency of Each Prime in Factorization:

আমরা প্রতিটা নাম্বার এর প্রাইম ফ্যাক্টোরাইজেশনের সময় freq[][] অ্যারেটা তৈরি করে নিতে পারি। যখন কোন প্রাইম পাব, তার সিরিয়াল নাম্বার আছে maap[] নামের অ্যারেতে । যদি ঐ প্রাইম tot বার পাওয়া যায়, তবে আমরা freq[maap[pf]][tot]++ করে দেব, যেখানে pf হলো প্রাইম ফ্যাক্টর ।

Using Cumulative Sum aka Prefix Sum: 

আমরা freq[][] নামের একটা 2D অ্যারে নেব, freq[i][j] স্টোর করবে i তম প্রাইম j বার আছে অ্যারের কতগুলো নাম্বারে ।

আমরা চাই freq[i][j] স্টোর করবে i তম প্রাইম j বার বা j এর চেয়ে বেশি বার আছে অ্যারের কতগুলো নাম্বারে । এজন্য আমরা প্রতি i তম প্রাইম এর লুপের ভিতরে freq[i][j] = freq[i][j+1] করে দিলেই হবে ।

Calculating answer:

যদি মোট c টা প্রাইম থাকে ১৫০০০০০০ পর্যন্ত, তবে প্রতি প্রাইম এর জন্য আমাদের দেখতে হবে সেই প্রাইম GCD তে আছে কতবার, এবং তার চেয়ে বেশি বার আছে কতগুলো নাম্বারে। যতগুলো নাম্বারে তার চেয়ে বেশি বার আছে, সেই নাম্বার গুলো অ্যারেতে রেখে বাকিগুলো রিমুভ করে দিলে এই রেখে দেয়া নাম্বারগুলোর GCD সবগুলো নাম্বার এর GCD এর চেয়ে বড় হবে ।
এভাবে প্রতিটা প্রাইম নাম্বার এর জন্য দেখতে হবে, কতগুলো নাম্বার রিমুভ করতে হবে এবং এদের মাঝে সর্বনিম্নটাই হবে answer.
যদি সবগুলো নাম্বারই রিমুভ করতে হয়, অর্থাৎ answer যদি n হয় ( এটা তখনই হবে, যদি অ্যারের সব নাম্বারই একই হয়), তবে output হবে -1.

সম্পূর্ণ কোডঃ

কোডফোর্সেসে আমার সলিউশন এর রান টাইম ছিল 0.358 second, টাইম লিমিট ছিল 1 second.

Codeforces এ সাবমিশন লিংকঃ https://codeforces.com/contest/1047/submission/48318621

সম্পূর্ণ কোডটা নিচে দিয়ে দিলাম -

তাহলে আজ এ পর্যন্তই । সামনের পর্বে এই প্রোবলেম এর আরো কিছু সলিউশন নিয়ে আলোচনা করব ।
আল্লাহ হাফেজ । হ্যাপি কোডিং ।