Secret Signal

View as PDF

Submit solution

Points: 5
Time limit: 3.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

The Alliance, which was at war with Collea, uses a highly convoluted method to encrypt their messages which involves signaling a long series of positive integers. Despite their best attempts, Collea was unable to effectively decrypt their messages. However, they have found out that a sequence of these signals might be an encrypted message if and only if the sum of the integers signalled is a multiple of K. The Alliance had just signalled N integers. Help the Collean Armed Forces find how many continuous intervals of these signals might contain an encrypted message.


1 \le N \le 200\,000
1 \le K \le 50\,000
1 \le a_i \le 1\,000\,000

Input Specification

The first line contains two positive integers, N and K.
The next line contains N positive integers, the numbers a_1,a_2,\dots,a_N.

Output Specification

Print one integer, the number of intervals of the signals whose elements sum to a multiple of K.

Sample Input

5 4
60 2 7 1 2

Sample Output



  • 2
    JustinXu  commented on Dec. 31, 2018, 7:13 p.m. edited

    Edit: it was fixed