TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

75.8% (25/33)

Submission's AC Ratio

24.9% (96/385)

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

注意:本題沒有輸入,本輸入為提供測試標頭檔(參見Hints)使用。
6
5 3 6 2 4 9
3
1 3
2 5
1 5

Sample Output

注意:本題沒有輸出,本輸出為提供測試標頭檔(參見Hints)使用。
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

For Testdata: 0 ~ 3, Score: 11
For Testdata: 0 ~ 7, Score: 13
For Testdata: 0 ~ 11, Score: 27
For Testdata: 13 ~ 14, Score: 23
For Testdata: 0 ~ 15, Score: 26
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 600 409600 262144
1 600 409600 262144
2 600 409600 262144
3 600 409600 262144
4 300 409600 262144
5 300 409600 262144
6 300 409600 262144
7 300 409600 262144
8 1800 409600 262144
9 1800 409600 262144
10 1800 409600 262144
11 1800 409600 262144
12 5700 409600 262144
13 6500 409600 262144
14 6500 409600 262144
15 5700 409600 262144