P11129 [MX-X5-T1] "GFOI Round 1" Inverted World

Original link: 。 --- > [Inverted World - ARForest](https://music.163.com/#/song?id=2099631232)

Given a positive integer sequence $(a_1, \ldots, a_n)$ of length $n$, it is **guaranteed that this sequence is an arithmetic progression**。 (If you do not know the definition of an arithmetic progression, please refer to the hint at the end of the statement.) Please find the number of non-empty contiguous subarrays $(a_l, \ldots, a_r)$ ($1 \le l \le r \le n$) in this sequence that satisfy: - The average of the elements in the subarray is an integer。 (That is, $(a_l + \cdots + a_r) \div (r - l + 1)$ is an integer.) The sequence may be very long, i.e., $n$ can be very large, so the full sequence will not be given. Instead, only the length $n$, the first term $k$, and the common difference $d$ are given. It is **guaranteed that $\bm{k, d}$ are both positive integers**。

**This problem contains multiple test cases。** The first line contains a positive integer $T$, representing the number of test cases。 For each test case: The first line contains three positive integers $n, k, d$。

For each test case, output one line containing a non-negative integer, representing the number of subarrays whose average is an integer。

**[Sample Explanation]** In the first test case, $a = [1, 3]$。There are $3$ non-empty contiguous subarrays that satisfy the requirement: - $[1]$, whose average is $1$； - $[3]$, whose average is $3$； - $[1, 3]$, whose average is $2$。 In the second test case, $a = [2, 7, 12]$。There are $4$ non-empty contiguous subarrays that satisfy the requirement: - $[2]$, whose average is $2$； - $[7]$, whose average is $7$； - $[12]$, whose average is $12$； - $[2, 7, 12]$, whose average is $7$。 **[Constraints]** | Test Point ID | $n \le$ | $k \le$ | $d \le$ | Score | | :-: | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $10$ | $28$ | | $2$ | $10^9$ | $10^9$ | $1$ | $35$ | | $3$ | $10^9$ | $10^9$ | $10^9$ | $37$ | For all testdata, it holds that $1 \le T \le 10^3$, $1 \le n, k, d \le 10^9$。 **[Definition Hint]** An arithmetic progression of length $n$ with first term $k$ and common difference $d$ is defined as $a_1 = k$ and $a_i = a_{i - 1} + d$ (for every $2 \le i \le n$)。 Translated by ChatGPT 5