All submissions for this problem are available.
Chef's restaurant is the most attractive place to have dinner at. To understand why, let's have a look at a way customers do their orders:
There is only one list of N ingredients in the menu. Every ingredient has its beauty value that does not depend on its taste, but on the way it looks, which is expressed as a positive integer. To order a dish, the customer asks Chef to use all the ingredients from L to R (L is strictly less than R). Chef knows that the dish will be tasty and not only beautiful if the sum of its ingredients' beauty values is divisible by K. Chef does not want to use all the ingredients, so he always excludes one of them. Which one? - The least beautiful one! (in other words - which has the minimal beauty value). Now he wonders - how many segments (L,R) are there such that the sum of their beauty values will be divisible by K after excluding the least beautiful ingredient.
First line of the input consists of two positive integers - N and K. There are N space separated positive integers - beauty values of the ingredients.
Output should consist of a single integer - the answer for the problem.
1 ≤ N ≤ 2*105 1 ≤ K ≤ 109 1 ≤ beauty value ≤ 109
4 2 1 2 3 4
1 ≤ N ≤ 1000, this subtask is worth 21 point.
1 ≤ K ≤ 100, this subtask is worth 39 points.
There are no special constrains for the remaining 40 points.
Test generation details:
Delivery and sorting of ingredients is quite random thing, so all the test cases will look as follows:
N and K are chosen by setter. An integer M is chosen by setter from interval [100..10^9]. Let B be the array of beauty values of ingredients. B[i] is chosen uniformly at random from an interval [1..M] for every 1 ≤ i ≤ N. After B is generated setter can choose a positive integer R and do B[i] = B[i]*R for every 1 ≤ i ≤ N. It's guaranteed that even after multiplying every B[i] won't exceed 10^9.
|Tags||Rubanenko, divide-and-conq, ltime01, medium|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.