Practice on Toph

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

Divisible LCM

By adnan_toky · Limits 1s, 512 MB

You have a sequence a1, a2, a3, , ana_1,~ a_2,~ a_3,~…, ~a_n of n integers and qq queries. In each query, you are given three integers ll, rr and xx. You have to answer the following question:

Is it possible to select some integers from the segment al, al+1, al+2,  ara_l,~ a_{l+1}, ~a_{l+2},~\dots~ a_r such that their LCM is divisible by xx and no two consecutive integers are selected? That is, if you select aia_i, you cannot select ai+1a_{i+1}.

Here LCM means the Least Common Multiple of numbers.


The first line of input contains two space-separated integers nn and qq (1n,q105)(1 \leq n, q \leq 10^5) denoting the number of integers and the number of queries.

The next line contains nn space-separated integers a1, a2, a3, , ana_1, ~a_2, ~a_3,~…, ~a_n (1ai105)(1 \leq a_i \leq 10^5).

Following qq lines contain three integers each. ll, rr and xx (1lrn,1x105)(1 \leq l \leq r \leq n, 1 \leq x \leq 10^5).


For each query, print Yes or No in a single line, the answer to the query.


6 5
4 7 3 5 12 22
1 5 10
2 5 10
5 5 12
3 5 10
1 4 20



50% Solution Ratio

adnan_tokyEarliest, 1M ago

adnan_tokyFastest, 0.4s

adnan_tokyLightest, 14 MB

adnan_tokyShortest, 2292B


Login to submit


Short Tutorial: There are at most 666 distinct prime factors of a number nnn where n≤105n \leq 10^5n...

Related Contests

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