RANPRO Editorial

PERFECT_PRODUCT EDITORIAL.
Problem Link:- RANPRO

SETTER : @jprm2
Editorialist : @jprm2

Difficulty : Easy-Medium

Pre-Requisites : Segment-Tree , Number Theory , Maths.

EXPLANATION

Problem was pretty straight forward that you want to find product in a range of array and update the elements in the queries of type 2.

where in each update operation you will multiply the number present at any given index by the given number . And in queries of type one you have to answer.

whether the product of numbers in the range is a perfect square or not.

In both of the queries your main point is that you have to find product of numbers in the given range.Thus as per constraints if you will find the product
and try to store in any data type then it will overflow. So to preserve the number you were given another observation that the highest prime factor of any
number of a array or in query is less than 100.

Making use of above given fact this problem can be solved very easily. What we can do is that each array index we can store a vector of length 100 which
will store the prime factorization of the given number for example if number is 12 then vectors initial values will be like {0,0,2,1,0,0,0…} since prime
factorization of 12 =223 so at index 2 we inserted power of 2 and at index 3 we inserted 1 because power of 3 is 1.

This generation of prime factorization
of a number takes log(n) time only you can study about this from here https://codeforces.com/blog/entry/7262

Now suppose our array is of 2 size and it is like
12 3. After prime factorization it looks like:-

{0,0,2,1,0,0},{0,0,0,1,0,0}; two vectors will be of full 100 size only but all further zeroes are truncated. now you might know that for finding the product

of two numbers you basically sum the powers of their primes so we find the sum of powers of primes for a particular prime number till 100 index and thus when
we sum these 2 given vectors then it becomes {0,0,2,2,0,0} now if in this final produced vector if all numbers are even(divisible by 2) then the product is a
perfect square. if any value in the produced product vector is odd then the number is not a perfect square.

Thus your main task is to find the sum of powers of a particular prime number in the given range in a query of type 1 from l to r and this is also not a tough task.

For range summation queries and index update query you can use any of the fenwick or segment trees with a vector of length 100 as a node because all primes
are less than or equal to 100. keeping this sum is not a difficult task. finding this sum in a range can be done easily just return vector as answer of a query.

We will use segment trees only for finding the sum of powers of a particular prime in a given range and for update query with multiplying the value at index
i with val we can do easily just by prime factorizing the given value and adding the corresponding powers of this index’s prime factor…

For example value at index 3 is 3({0,0,0,1,0,0}) thus after multiplying this value with 9({0,0,0,2,0,0}) then the value becomes 27 which is nothing but
{0,0,0,1,0,0}+{0,0,0,2,0,0}={0,0,0,3,0,0};

Thus this problems becomes very easy all you have to implement is with segment trees that range summation of powers of particular
prime number and source to study that. https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/

Setter’s and Editorialist’s Solution:

Setters and Editorialists Solutions.

Solution Link.

Hope you liked it and feel free to share any approach or ask any doubts in comments below. Other optimal solutions are encouraged too.

4 Likes

@anon31329220 Link is not accessible

@cubefreak777 Solution link updated sorry for inconvenience.

That means I have to create a segment tree with each node containing 100 size array storing prime powers of the numbers and run segment tree on them in range to find the sum of powers of the primes in the respective ranges right?