 # DCP-537: Easy Modulo Shift Back to All Problems

Easy Math > Counting

Professor Mahammad likes playing with arrays, today he invented another interesting game for you. Here it is. Professor defines **goodness values** of array **a** over a fixed value **M** as the number of subarrays (contiguous subsequence) of this array having the sum divisible by **M**. Let's define this goodness value as **g(a, M)**. For example, if **a = [2, 3, 4, 2] and M = 3**, we get **g(a, M) = 4** because the following **4** subarrays have a sum which is multiple of **M**: **{[2, 3, 4]; , [3, 4, 2], [4, 2]}**. Now, consider all possible **cyclic shifts** of the array **a**, surely we have **N** of them. Your task is quite simple, just find the number of cyclic shifts of **a** which have maximum goodness value over the given **M**. Input: ------ The very first line of the input contains an integer **T (1 ≤ T ≤ 10)**, denoting the number of test cases. Each test case consists of 2 lines. The first one contains an integer **N (1 ≤ N ≤ 10^3)** and **M (1 ≤ M ≤ 10^5)** denoting the number of elements of the array and the fixed number **M**, respectively. The next line will contain **4** integers separated by spaces, denoting **a**, **A**, **B** and **C (1 ≤ a, A, B, C ≤ 10^5)** . Simply, you are given **a** and other remaining elements can be calculated as **a[i] = (a[i - 1] * A + B) % C** where **2 ≤ i ≤ n**. Output: ------- For each test case, print an integer, describing the number of cyclic shifts having maximum goodness value. Sample Input ------------ 1 3 2 5 4 10 9 Sample Output ------------- 2 Note: After generation, our array will be **a = [5, 3, 4]** and **M = 2** is given. 1st cyclic shift of **a** --> [5, 3, 4], g(a, M) = **3**; **{[5, 3], [5, 3, 4], }** are good subarrays. 2nd cyclic shift of **a** --> [3, 4, 5] g(a, M) = **2**; **{, [3, 4, 5]}** are good subarrays. 3rd cyclic shift of **a** --> [4, 5, 3] g(a, M) = **3**; **, [4, 5, 3], [5, 3]}** are good subarrays. Since 1st and 3rd cyclic shifts have the maximum goodness value 3, answer is 2.

### Problem Limits

 Language Time Limit (seconds) C 2.00 C++ 2.00 C++14 2.00 C# 3.00 Go 3.00 Java 3.00 JavaScript 3.00 Objective-C 3.00 Perl 3.00 PHP 3.00 Python 3.00 Python3 3.00 Ruby 3.00 VB.Net 3.00

# 28/159

Solve/Submission

### Ranking

# User Language Timing
01 tariqiitju Cpp 0.00s
02 feodorv C 0.03s
03 skmonir Cpp14 0.09s
04 emrul Cpp 0.10s
05 kashem1993 Cpp 0.11s
06 _cicipi_ Cpp14 0.13s
07 spectro30 Cpp 0.13s
08 Taran Cpp14 0.14s
09 Reayz Cpp14 0.15s
10 yasirnabil534 Cpp 0.19s
11 DynamicOvi Cpp14 0.21s
12 Hasinur_ Cpp 0.25s
13 shahed95 Cpp 0.25s
14 steinum Cpp14 0.27s
15 SakibAlamin Cpp14 0.29s
16 ssavi Cpp 0.32s
17 m_arif Cpp14 0.32s
18 ashraful_afruz Cpp 0.38s