Preparing NOJ

Divisible Subsequences

10000ms 65536K

Description:

Given a sequence of positive integers, count all contiguous subsequences (sometimes called substrings, in contrast to subsequences, which may leave out elements) the sum of which is divisible by a given number. These subsequences may overlap. For example, the sequence (see sample input)

2; 1; 2; 1; 1; 2; 1; 2

contains six contiguous subsequences the sum of which is divisible by four: the rst to eighth number, the second to fourth number, the second to seventh number, the third to fth number, the fourth to sixth number, and the fth to seventh number.


Input:

The rst line of the input consists of an integer c (1 <= c <= 200), the number of test cases. Then follow two lines per test case.

Each test case starts with a line consisting of two integers d (1 <= d <= 1 000 000) and n (1 <= n <= 50 000), the divisor of the sum of the subsequences and the length of the sequence, respectively. The second line of a test case contains the elements of the sequence, which are integers between 1 and 1 000 000 000, inclusively.


Output:

For each test case, print a single line consisting of a single integer, the number of contiguous subsequences the sum of which is divisible by d.


Sample Input:

2
7 3
1 2 3
4 8
2 1 2 1 1 2 1 2

Sample Output:

0
6

Note:

本题由旧版NOJ导入,来源:NWERC2009

Info

NOJ

Provider NOJ

Code NOJ1143

Tags

Submitted 3

Passed 1

AC Rate 33.33%

Date 04/20/2019 10:03:10

Related

Nothing Yet