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 করতে হবে । এ জন্য আমরা প্রথমে সিভ চালিয়ে প্রতিটা নাম্বার এর সর্বনিম্ন প্রাইম ফ্যাকটর বের করে নেব ।

	typedef long long ll;
	const int M = 15000000;
	bool is_composite[M+2];
	int sp[M+2]; // smallest prime factor of i
	int freq[970710][25]; // freq[i][j] = k means that there are k numbers in array
	// in which i'th prime occurs j or more times
	int maap[M+2]; // maap[i] = k means that i is k'th prime
	int c = 0; // number of prime
	int cnt[970710]; // cnt[i] = frequency of i'th prime in gcd
	void Sieve(){
	for (int i = 2; i <= M; i += 2)
	sp[i] = 2;
	maap[2] = ++c;
	for (ll i = 3; i <= M; i += 2){
	if (is_composite[i]) continue;
	sp[i] = i;
	maap[i] = ++c;
	for (ll j = i; (j*i) <= M; j += 2){
	if (!is_composite[j*i]){
	is_composite[j*i] = true;
	sp[j*i] = i;
	}
	}
	}
	}

view raw sieve.cpp hosted with ❤ by GitHub

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

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

	void prime_in_gcd(int n)
	{
	while(n>1){
	int pf = sp[n];
	while(n%pf==0)
	n/=pf, cnt[maap[pf]]++;
	}
	}

view raw factorization.cpp hosted with ❤ by GitHub

যেহেতু কোন নাম্বার এর সর্বোচ্চ 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 হলো প্রাইম ফ্যাক্টর ।

	void factorize(int n)
	{
	while(n>1){
	int tot = 0, pf = sp[n];
	while(n%pf==0)
	n/=pf, tot++;
	freq[maap[pf]][tot]++;
	}
	}

view raw frequency of prime factor.cpp hosted with ❤ by GitHub

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] করে দিলেই হবে ।

	for(int i=1;i<=c;i++)
	for(int j =23;j>=1;j--)
	freq[i][j]+=freq[i][j+1];

view raw prefix sum.cpp hosted with ❤ by GitHub

Calculating answer:

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

	int mini = n;
	for(int i=1;i<=c;i++){
	int k = cnt[i];
	int del = n - freq[i][k+1];
	mini = min(mini, del);
	}
	if(mini==n) printf("-1\n");
	else printf("%d\n", mini);

view raw calculating answer.cpp hosted with ❤ by GitHub

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

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

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

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

	#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	const int M = 15000000;
	bool is_composite[M+2];
	int sp[M+2]; // smallest prime factor of i
	int freq[970710][25]; // freq[i][j] = k means that there are k numbers in array
	// in which i'th prime occurs j or more times
	int maap[M+2]; // maap[i] = k means that i is k'th prime
	int c = 0; // number of prime
	int cnt[970710]; // cnt[i] = frequency of i'th prime in gcd
	void Sieve(){
	for (int i = 2; i <= M; i += 2)
	sp[i] = 2;
	maap[2] = ++c;
	for (ll i = 3; i <= M; i += 2){
	if (is_composite[i]) continue;
	sp[i] = i;
	maap[i] = ++c;
	for (ll j = i; (j*i) <= M; j += 2){
	if (!is_composite[j*i]){
	is_composite[j*i] = true;
	sp[j*i] = i;
	}
	}
	}
	}
	void factorize(int n)
	{
	while(n>1){
	int tot = 0, pf = sp[n];
	while(n%pf==0)
	n/=pf, tot++;
	freq[maap[pf]][tot]++;
	}
	}
	void prime_in_gcd(int n)
	{
	while(n>1){
	int pf = sp[n];
	while(n%pf==0)
	n/=pf, cnt[maap[pf]]++;
	}
	}
	int main()
	{
	Sieve();
	int n;
	scanf("%d", &n);
	int g = 0;
	for(int i=1;i<=n;i++){
	int x;
	scanf("%d", &x);
	g =__gcd(x, g);
	factorize(x);
	}
	prime_in_gcd(g);
	for(int i=1;i<=c;i++)
	for(int j =23;j>=1;j--)
	freq[i][j]+=freq[i][j+1];
	int mini = n;
	for(int i=1;i<=c;i++){
	int k = cnt[i];
	int del = n - freq[i][k+1];
	mini = min(mini, del);
	}
	if(mini==n) printf("-1\n");
	else printf("%d\n", mini);
	return 0;
	}

view raw solution_cf_1047c.cpp hosted with ❤ by GitHub

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