1338 . 因數元素

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

80.5% (107/133)

Submission's AC Ratio

22.2% (367/1650)

Tags

CKsim 2016-CKsim-3rd IOIstyle

Description

現在你有一個長度為N的正整數序列C0,C1,⋯,CN−1。
對於這個序列的某個連續子序列C[L,R)，定義這個連續子序列的「因數元素」為一個範圍內的數Ci（L≤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≤106,Q≤2×107。

子任務（測資） 額外限制 分數
1 (0~3) N,Q≤800 11
2 (0~7) N,Q≤3000 13
3 (0~11) N,Q≤2×105 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

Sample Output 1

注意：本題沒有輸出，本輸出為提供測試標頭檔（參見Hints）使用。
1
1
0

Hints

這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受以下輸入，數字間皆以空白分隔：
第一行：N；
第二行：C0,C1,⋯,CN−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 (VSS, 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 6200 409600 262144 5
13 7200 409600 262144 4 5
14 7200 409600 262144 4 5
15 6200 409600 262144 5
Submit
Back to Top