TopCoder

WeaK
weak.infor.org 雖然這裡好像沒什麼東西。

User's AC Ratio

100.0% (9/9)

Submission's AC Ratio

15.2% (15/99)

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

For Testdata: 0 ~ 4, Score: 13
For Testdata: 0 ~ 9, Score: 28
For Testdata: 10 ~ 14, Score: 37
For Testdata: 0 ~ 19, Score: 22
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 1000 65536 65536
17 1000 65536 65536
18 1000 65536 65536
19 1000 65536 65536