TopCoder

Adrien Wu
AC×29New TIOJ ?

User's AC Ratio

93.3% (28/30)

Submission's AC Ratio

25.8% (68/264)

Tags

Description

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

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

Input Format

第一行包含兩個正整數N105,Q106,分別代表卷軸長度以及詢問個數。
第二行包含N個正整數c0,c1,,cN1,代表N個格子內含有的數字。
接下來的Q行中,每一行有兩個整數0i,j<N,代表兩人的起始位置。

子任務(測資) 額外限制 分數
1 (0~4) N,Q103 13
2 (0~9) N103 28
3 (10~14) ci=1 or 109+6 37
4 (0~19) 22

Output Format

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

Sample Input 1

4 2
1 1000000006 1 1000000006
0 2
2 1

Sample Output 1

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 (VSS, 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