TopCoder

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

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

25.5% (38/149)

Description

在一個多人單向卷軸遊戲中,有$N\leq 10^ 5$個格子,每個格子都有一個不超過$10^ 9+6$的正整數,代表該格的狀況。
有時遊戲中的兩人會產生「同步」的現象。產生同步的條件是兩人所在的格子的數字$a,b$分別滿足$(ab)^ {\frac{p-1}{2}}\equiv 1\mod p$,其中$p=10^ 9 + 7$。產生同步後,兩人會瞬移至下一格。如果在下一格又產生「同步」,則會繼續往下走,直到其中一人超出格子範圍(到了終點了)或者兩人不再同步。

給定$N$個格子中的正整數以及兩人的起始位子,請計算他們兩個將會「同步」幾次。

Input Format

第一行包含兩個正整數$N\leq 10^ 5, Q\leq 10^ 6$,分別代表卷軸長度以及詢問個數。
第二行包含$N$個正整數$c_0,c_1,\dots,c_{N-1}$,代表$N$個格子內含有的數字。
接下來的$Q$行中,每一行有兩個整數$0\leq i,j < N$,代表兩人的起始位置。

子任務(測資) 額外限制 分數
1 (0~4) $N,Q\leq 10^ 3$ 13
2 (0~9) $N\leq 10^ 3$ 28
3 (10~14) $c_i=1\text{ or }10^ 9+6$ 37
4 (0~19) 22

Output Format

對於每筆詢問,請輸出兩人同步的次數。

Sample Input

4 2
1 1000000006 1 1000000006
0 2
2 1

Sample Output

2
0

Hints

本題的輸出量非常大,建議C++輸入輸出使用者加入std::cin.tie(0);以及ios_base::sync_with_stdio(0)兩行,以\n代替std::endl,同時不要使用C式輸出。

Problem Source

Problem set / Description by Paupière
建國中學105學年度校內第六次模擬賽pF

Subtasks

No. Testdata Range Score
1 0~4 13
2 0~9 28
3 10~14 37
4 0~19 22

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1 2 4
1 1000 65536 262144 1 2 4
2 1000 65536 262144 1 2 4
3 1000 65536 262144 1 2 4
4 1000 65536 262144 1 2 4
5 1000 65536 262144 2 4
6 1000 65536 262144 2 4
7 1000 65536 262144 2 4
8 1000 65536 262144 2 4
9 1000 65536 262144 2 4
10 1000 65536 262144 3 4
11 1000 65536 262144 3 4
12 1000 65536 262144 3 4
13 1000 65536 262144 3 4
14 1000 65536 262144 3 4
15 1000 65536 262144 4
16 1000 65536 262144 4
17 1000 65536 262144 4
18 1000 65536 262144 4
19 1000 65536 262144 4