1927 . 同步(Sync)
TopCoder
Tags
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 1
4 2
1 1000000006 1 1000000006
0 2
2 1
1 1000000006 1 1000000006
0 2
2 1
Sample Output 1
2
0
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 |