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], [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[1]**, **A**, **B** and **C (1 ≤ a[1], A, B, C ≤ 10^5)** . Simply, you are given **a[1]** 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], [4]}** are good subarrays. 2nd cyclic shift of **a** --> [3, 4, 5] g(a, M) = **2**; **{[4], [3, 4, 5]}** are good subarrays. 3rd cyclic shift of **a** --> [4, 5, 3] g(a, M) = **3**; **[4], [4, 5, 3], [5, 3]}** are good subarrays. Since 1st and 3rd cyclic shifts have the maximum goodness value 3, answer is 2.


Problem Setter:

Mahmud Allahverdiyev

Please login to submit solution to this problem.

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

Problem Stats

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 spectro30 Cpp 0.13s
07 _cicipi_ Cpp14 0.13s
08 Taran Cpp14 0.14s
09 Reayz Cpp14 0.15s
10 yasirnabil534 Cpp 0.19s
11 DynamicOvi Cpp14 0.21s
12 shahed95 Cpp 0.25s
13 Hasinur_ Cpp 0.25s
14 st3inum 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
19 shahadat191 Cpp 0.67s
20 Essux Cpp 0.94s
21 Arpan_cse_2k14 Cpp 0.95s
22 iamsadee Cpp 1.20s
23 fayedanik Cpp 1.23s
24 Pure_Protea Cpp14 1.36s
25 unknown420 Cpp 1.40s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support