1338 . 因數元素
TopCoder
Tags
Description
現在你有一個長度為N的正整數序列$C_0, C_1, \cdots , C_{N-1}$。
對於這個序列的某個連續子序列$C_{[L, R)}$，定義這個連續子序列的「因數元素」為一個範圍內的數$C_i$（$L\leq i<R$），使得它可以整除每一個$C_{[L, R)}$之間的數。
給你$L, R$，試判斷這個連續子序列中存不存在「因數元素」。
Input Format
本題沒有輸入，如果你輸入了任何東西，可能會導致各種不可預期的結果。
請記得#include "lib1338.h"。你必須實作下列兩個函數：
void init(int N, long long C[]);：評測系統將會在執行的一開始呼叫這個函式，傳入正整數序列的長度N，以及長度為N的正整數陣列C。
int query(int L, int R);：呼叫完init後，將會連續呼叫Q次這個函式，傳入整數L, R（L < R）。如果[L, R)區間有因數元素，請回傳1，否則回傳0。
保證所有操作都是合法的。$N\leq 10^ 6, Q\leq 2\times 10^ 7$。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0~3) | $N, Q\leq 800$ | 11 |
| 2 (0~7) | $N, Q\leq 3000$ | 13 |
| 3 (0~11) | $N, Q\leq 2\times 10^ 5$ | 27 |
| 4 (13~14) | 無限制 | 23 |
| 5 (0~15) | 無限制 | 26 |
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Sample Input 1
注意：本題沒有輸入，本輸入為提供測試標頭檔（參見Hints）使用。
6
5 3 6 2 4 9
3
1 3
2 5
1 5
6
5 3 6 2 4 9
3
1 3
2 5
1 5
Sample Output 1
注意：本題沒有輸出，本輸出為提供測試標頭檔（參見Hints）使用。
1
1
0
1
1
0
Hints
這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：N；
第二行：$C_0, C_1, \cdots , C_{N-1}$；
第三行：Q；
接下來Q行：L, R；
對於每一次呼叫query函數，此程式會輸出函數回傳的數值。
Problem Source
Judge / Description by Yihda Yol
建國中學105學年度校內第三次模擬賽pA
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~3 | 11 |
| 2 | 0~7 | 13 |
| 3 | 0~11 | 27 |
| 4 | 13~14 | 23 |
| 5 | 0~15 | 26 |