[Tutorial] Toph - Is It A Square (solution)

Problem Description:

$N$ সাইজ বিশিষ্ট অ্যারে $A$ দেয়া আছে । এরপরে Q সংখ্যক কুয়েরি আছে । প্রতি কুয়েরিতে দুইটি সংখ্যা দেয়া আছে $l$ ও $r$ । 

বলতে হবে, অ্যারের $l$ থেকে $r$ পর্যন্ত সব সংখ্যা গুলিকে গুণ করলে গুণফল পুর্ণ বর্গ হবে কি না । 

Constraints:

$1 \space \leq N \space \leq \space 10^5$

$1 \space \leq Q \space \leq \space 10^5$

$-10^5 \space \leq A[i] \space \leq \space 10^5$

Problem Link: Is it A Square

Solution:

Prerequisite:

সলিউশনের জন্য আগে থেকেই যা যা জানা থাকতে হবে - 

1.  Cumulative Sum or Prefix Sum, or Cumulative Frequency Counting
2. Sieve of Eratosthenes
3. Prime Factorization
4. MO's Algorithm

যেহেতু $10^5$ টা সংখ্যাকে গুণ করলে তা স্টোর করা সম্ভব না, অতএব আমাদের Square Number এর অন্য কোন প্রোপার্টিজ ব্যবহার করতে হবে ।

একটি সংখ্যা পূর্ণ বর্গ হলে, তার প্রতিটা প্রাইম ডিভিজর জোড় সংখ্যক বার থাকে । যেমন, ৯ = ৩ * ৩,

৪ = ২*২*২*২, ২৫ = ৫*৫, ৩৬ = ২*২*৩*৩ ইত্যাদি ।

অতএব, আমরা অ্যারে এর প্রতিটা সংখ্যাকে প্রাইম ফ্যাক্টোরাইজেশন করে নেব । এরপরে দেখব, $l$ থেকে $r$ পর্যন্ত অ্যারের সংখ্যাগুলোকে গুণ করলে তাদের গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা ।

গুনফলে প্রতিটা প্রাইম ডিভিসর জোড় সংখ্যক বার আছে কিনা, সেটা আমরা MO's Algorithm ব্যবহার করে বের করব ।

odd নামের একটা global ভ্যারিয়েবল নেব, যার ভিতর থাকবে এখন পর্যন্ত মোট কয়টা প্রাইম ডিভিজর বিজোড় সংখ্যক বার আছে । 

MO's Algorithm এর প্রতি ধাপে যখন কোন ইন্ডেক্সে যাব, তখন সেই ইন্ডেক্সের সংখ্যাটির প্রতিটা প্রাইম ডিভিসর count এর মান 1 বাড়াবো (add এর ক্ষেত্রে ), অথবা 1 কমাবো (remove এর ক্ষেত্রে ) । প্রতিবার বাড়ানো বা কমানোর সময় চেক করব, ঐ প্রাইম ডিভিজর এর count এর বর্তমান মান এখন বিজোড় কিনা । যদি বিজোড় হয়, তবে odd এর মান এক বাড়াবো, বিজোড় না হলে odd এর মান এক কমাবো । ফুল রেঞ্জ iterate করার পরে যদি odd এর মান 0 হয় ( odd এর মান 0 মানে হলো, এখন পর্যন্ত বিজোড় সংখ্যক বার আছে এমন প্রাইম ডিভিজর এর পরিমাণ 0), তবে গুণফল Square নাম্বার হবে, নতুবা হবে না । 

তবে দুইটি কর্ণার কেস আছে :

1. যদি রেঞ্জের ভিতর এক বা একাধিক 0 থাকে, তবে গুণফল Square Number হবে । 
2. যদি রেঞ্জের ভিতরে বিজোড় সংখ্যক negative number থাকে, তবে গুণফল Negative Number হবে । অতএব এক্ষেত্রে গুণফল Square Number হবে না । 

তবে এই দুইটা কন্ডিশন আমরা Cumulative Sum এর সাহায্যে O(1) এই চেক করতে পারব ।


এই সলিউশনের complexity হবে $O((N+Q) . sqrt(N) . log n)$

Code:

	#include<bits/stdc++.h>
	using namespace std;
	#define ll long long
	#define vi vector<int>
	#define ii pair<int, int>
	#define pb push_back
	#define mp make_pair
	#define ff first
	#define ss second
	#define all(a) a.begin(), a.end()
	const int MX = 100000, bsiz = 320;
	bool p[MX+5];
	int cnt[MX+5], sp[MX+5], ara[MX+5], neg[MX+5];
	int zero[MX+5];
	vi prime_div[MX+5];
	int odd;
	vector<pair<ii, int> > queries;
	int ans[MX+5];
	void sieve()
	{
	p[0] = p[1] = 1;
	for(ll i = 2;i<=MX;i+=2)
	sp[i] = 2;
	int root = sqrt(MX);
	for(ll i=3;i<=MX;i+=2)
	{
	if(p[i]==0)
	{
	sp[i] = i;
	if(i>root)
	continue;
	for(ll j=i;j<=MX/i;j+=2)
	if(!p[i*j])
	p[i*j] = 1, sp[i*j] = i;
	}
	}
	}
	bool cmp(pair<ii, int > a, pair<ii, int > b)
	{
	if(a.ff.ff/bsiz==b.ff.ff/bsiz)
	return a.ff.ss<b.ff.ss;
	return a.ff.ff/bsiz < b.ff.ff/bsiz;
	}
	void add(int pos)
	{
	int sz = prime_div[pos].size(), x;
	for(int i = 0; i<sz; i++)
	{
	x = prime_div[pos][i];
	cnt[x]++;
	if(cnt[x]%2==1)
	odd++;
	else if(cnt[x] % 2 == 0)
	odd--;
	}
	}
	void remov(int pos)
	{
	int sz = prime_div[pos].size(), x;
	for(int i = 0; i<sz; i++)
	{
	x = prime_div[pos][i];
	cnt[x]--;
	if(cnt[x]%2==1)
	odd++;
	else if(cnt[x] % 2 == 0)
	odd--;
	}
	}
	int main()
	{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	sieve();
	int n, q;
	cin>>n>>q;
	neg[0] = 0;
	zero[0] = 0;
	for(int i = 1; i<=n; i++)
	{
	cin>>ara[i];
	neg[i] = neg[i-1];
	zero[i] = zero[i-1];
	if(ara[i]<0)
	neg[i]++;
	int x = abs(ara[i]);
	if(x==0)
	{
	zero[i]++;
	}
	while(x>1)
	{
	prime_div[i].pb(sp[x]);
	x/=sp[x];
	}
	}
	for(int i = 0; i<q; i++)
	{
	int l, r;
	cin>>l>>r;
	queries.pb(mp(mp(l, r), i));
	}
	sort(all(queries), cmp);
	int L = 1, R = 0;
	odd = 0;
	cur_ans = 1;
	for(int i = 0; i<q; i++)
	{
	int l = queries[i].ff.ff;
	int r = queries[i].ff.ss;
	int idx = queries[i].ss;
	if(zero[r] - zero[l-1]>0)
	{
	ans[idx] = 1;
	}
	else if((neg[r]-neg[l-1])%2==1)
	{
	ans[idx] = 0;
	}
	else
	{
	while(R<r)
	{
	R++;
	add(R);
	}
	while(R>r)
	{
	remov(R);
	R--;
	}
	while(L<l)
	{
	remov(L);
	L++;
	}
	while(L>l)
	{
	L--;
	add(L);
	}
	if(odd==0)
	ans[idx] = 1;
	else ans[idx] = 0;
	}
	}
	for(int i = 0; i<q; i++)
	if(ans[i])
	cout << "Yes\n";
	else cout << "No\n";
	return 0;
	}

view raw toph is it square.cpp hosted with ❤ by GitHub