Chia hết cho D
View as PDF
Submit solution
Points:
0.16 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một mảng ~a~ gồm ~n~ phần tử và một số nguyên dương ~D~. Nhiệm vụ của bạn là đếm số đoạn con liên tiếp của ~a~ mà có tổng các phần tử trong đoạn chia hết cho ~D~.
Input
Dòng đầu tiên gồm hai số nguyên dương ~n~ và ~D~ tương ứng với số phần tử của mảng ~a~ và hằng số ~D\ (1\le n,D\le 10^5)~.
Dòng thứ hai gồm ~n~ số nguyên ~a_1,a_2,\dots,a_n~ tương ứng với các phần tử trong mảng ~a\ (|a_i|\le 10^9)~.
Output
Gồm duy nhất một giá trị là số đoạn con thỏa mãn.
Sample Input 1
5 4
1 3 -2 3 -5
Sample Output 1
4
Notes
Có bốn đoạn con thỏa mãn điều kiện của đề bài:
Đoạn con ~[1;2]~ do ~a_1+a_2=1+3=4~ chia hết cho ~4~.
Đoạn con ~[1;5]~ do ~a_1+a_2+a_3+a_4+a_5=1+3-2+3-5=0~ chia hết cho ~4~.
Đoạn con ~[2;4]~ do ~a_2+a_3+a_4=3-2+3=4~ chia hết cho ~4~.
Đoạn con ~[3;5]~ do ~a_3+a_4+a_5=-2+3-5=-4~ chia hết cho ~4~.
Comments
Ai cha dung prefix