18651번 - Linear Congruential Generator 다국어

문제

You are given a generator defined by the recurrence relation

\[X_{n+1} = ((a X_n + c) \mod {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_{i=l_2}^{r_2}(X_i \mod {(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\).

출력

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.

제한

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

힌트

In the first sample case, \(X = \{X_n\}_{n=0}^{\infty} = \{1, 5, 2, 6, 3, 0, \dots\}\).

In the second sample case, \(X = \{X_n\}_{n=0}^{\infty} = \{1, 9, 3, 5, \dots\}\).