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:
সলিউশনের জন্য আগে থেকেই যা যা জানা থাকতে হবে -
- Cumulative Sum or Prefix Sum, or Cumulative Frequency Counting
- Sieve of Eratosthenes
- Prime Factorization
- 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 নাম্বার হবে, নতুবা হবে না ।
তবে দুইটি কর্ণার কেস আছে :
- যদি রেঞ্জের ভিতর এক বা একাধিক 0 থাকে, তবে গুণফল Square Number হবে ।
- যদি রেঞ্জের ভিতরে বিজোড় সংখ্যক negative number থাকে, তবে গুণফল Negative Number হবে । অতএব এক্ষেত্রে গুণফল Square Number হবে না ।
এই সলিউশনের complexity হবে $O((N+Q) . sqrt(N) . log n)$