Pairwise Coprime Segments

2 secs 1024 MB
milkcoffee's icon milkcoffee

配点 : 500500

問題文

NN 個の正整数からなる数列 AA が与えられます。 また、以下のようなクエリが QQ 個与えられます。

  • 数列 AA は区間 [L,R][L,R] において「pairwise coprime」ですか?

ただし、「Li<jRL \leq i < j \leq R となる全ての (i,j)(i,j) の組について、gcd(Ai,Aj)=1\mathrm{gcd}(A_i, A_j)=1」のとき、
かつそのときに限り、数列 AA は区間 [L,R][L,R] において「pairwise coprime」であるといいます。
gcd\mathrm{gcd} は最大公約数を表します。

各クエリに答えてください。

制約

  • 2N1052 \leq N \leq 10^{5}
  • 2Ai1042 \leq A_i \leq 10^{4} (1iN)(1 \leq i \leq N)
  • 1Q1041 \leq Q \leq 10^{4}
  • 1Li<RiN1 \leq L_i < R_i \leq N (1iQ)(1 \leq i \leq Q)
  • 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられます。

NN QQ
A1A_1 A2A_2 \cdots ANA_N
L1L_1 R1R_1
L2L_2 R2R_2
\vdots
LQL_Q RQR_Q

出力

各クエリについて、数列 AA は区間 [L,R][L,R] において「pairwise coprime」であるならば「Yes」、そうでなければ「No」を出力してください。
ii 個目のクエリに対する答えを ii 行目に出力してください。

サンプル 1

入力1
10 5
2 4 8 8 7 15 6 9 4 11
1 5
4 6
4 7
8 10
2 3
出力1
No
Yes
No
Yes
No

11 つ目のクエリについて、例えば

  • gcd(A1,A2)=gcd(2,4)=2\mathrm{gcd}(A_1, A_2)=\mathrm{gcd}(2, 4)=2

となるため、区間 [1,5][1,5] において「pairwise coprime」ではありません。

22 つ目のクエリについて、

  • gcd(A4,A5)=gcd(8,7)=1\mathrm{gcd}(A_4, A_5)=\mathrm{gcd}(8, 7)=1
  • gcd(A4,A6)=gcd(8,15)=1\mathrm{gcd}(A_4, A_6)=\mathrm{gcd}(8, 15)=1
  • gcd(A5,A6)=gcd(7,15)=1\mathrm{gcd}(A_5, A_6)=\mathrm{gcd}(7, 15)=1

となるため、区間 [4,6][4,6] において「pairwise coprime」です。

提出


Go (1.21)