TopCoder

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

User's AC Ratio

82.1% (46/56)

Submission's AC Ratio

20.1% (133/661)

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

No. Testdata Range Score
1 0~3 11
2 0~7 13
3 0~11 27
4 13~14 23
5 0~15 26

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 600 409600 262144 1 2 3 5
1 600 409600 262144 1 2 3 5
2 600 409600 262144 1 2 3 5
3 600 409600 262144 1 2 3 5
4 300 409600 262144 2 3 5
5 300 409600 262144 2 3 5
6 300 409600 262144 2 3 5
7 300 409600 262144 2 3 5
8 1800 409600 262144 3 5
9 1800 409600 262144 3 5
10 1800 409600 262144 3 5
11 1800 409600 262144 3 5
12 5700 409600 262144 5
13 6500 409600 262144 4 5
14 6500 409600 262144 4 5
15 5700 409600 262144 5