Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Is It A Square?

By fsshakkhor · Limits 1.5s, 512 MB

Shikamaru is the most brilliant student of his class. He is very good at Mathematics. Mr. Asuma is their math teacher. Today he taught the class about square numbers. A square number is a non-negative integer which is the product of some integer with itself. For example, 0, 1, 4, 9, 16, 25 are square numbers, but 2, 3, 5, 6 are not. Mr. Asuma wanted to test whether his students can identify square numbers or not. So he gave them a homework.

He gave them an array A[ consisting of n integers and asked q questions. In each question, he gave them two integers l and r which denotes two positions of the array. The students have to tell whether the product of all the integers between the two positions (l and r inclusive) is a square number or not. In other words, they have to compute the value of P represented as the following:

P=i=lrAi P = \prod\limits_{i=l}^r A_i

And check whether it is a square or not. The array follows 1-based indexing.

After returning home, Shikamaru started doing his homework. He was able to answer some of the questions correctly, but later some of the products P became so huge and he could not identify whether they are square or not. Can you help Shikamaru doing his homework?


The first line contains two integers n (1 ≤ n ≤ 105) and q (1 ≤ q ≤ 105). The second line contains n integers A1, A2, ... , An ( -105 ≤ Ai ≤ 105 ). Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ n).


For each question print "Yes" if the product is a square, otherwise print "No" in a separate line.


6 4
4 1 2 0 -3 -3
1 1
2 3
4 4
5 6

For the first input, the product is 4. It is a square number.

For the second input, the product is 1×2 = 2. It is not a square number.

For the third input, the product is 0. It is a square number.

For the fourth input, the product is (-3)×(-3) = 9. It is a square number.



46% Solution Ratio

NirjhorEarliest, Jun '17

steinumFastest, 0.0s

nitaibanikLightest, 1.8 MB

steinumShortest, 643B


Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.