Background

Original link: https://oier.team/problems/X5B。

Inverted World - ARForest

Problem Description

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。

Input Format

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$。

Output Format

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

3
2 1 2
3 2 5
11451 41 91981

3
4
32787076

Hint

[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]

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