409637: GYM103652 B Linear Congruential Generator

You are given a generator defined by the recurrence relation

$$$$$$X_{n + 1} = ((a X_n + c) \bmod m),$$$$$$

where $$$X = \{X_n\}_{n = 0}^{\infty}$$$ is the generated sequence of pseudorandom values, and $$$m$$$, $$$a$$$, $$$c$$$, $$$X_0$$$ are integer constants which specify the generator.

Additionally, two integer intervals $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ are given. Please calculate

$$$$$$\sum_{i = l_1}^{r_1}\sum_{j = l_2}^{r_2}{(X_i \bmod (X_j + 1))}$$$$$$

The input contains several test cases. The first line contains an integer $$$T$$$ indicating the number of test cases. The following describes all test cases. For each test case:

The only line contains eight integers $$$m, a, c, X_0, l_1, r_1, l_2, r_2$$$.

• $$$1 \leq T \leq 10^5$$$
• $$$1 \leq m \leq 10^6$$$
• $$$0 \leq a, c, X_0 < m$$$
• $$$0 \leq l_1 \leq r_1 \leq 10^6$$$
• $$$0 \leq l_2 \leq r_2 \leq 10^6$$$
• The sum of $$$m$$$ in all test cases does not exceed $$$2 \times 10^6$$$.

For each test case, output a line containing "Case #x: y" (without quotes), where x is the test case number starting from $$$1$$$, and y is the answer to this test case.

2
7 1 4 1 2 3 4 5
10 3 6 1 2 3 1 2

Case #1: 4
Case #2: 12

In the first sample case, $$$\{X_n\}_{n = 0}^{\infty} = \{1, 5, 2, 6, 3, 0, \ldots\}$$$.

In the second sample case, $$$\{X_n\}_{n = 0}^{\infty} = \{1, 9, 3, 5, \ldots\}$$$.