Tổng bộ phận

View as PDF

Submit solution


Points: 0.38 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
Indian Computing Olympiad, Online Programming Contest, July 06
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một dãy gồm ~N~ (~1 \leq N \leq 10^5~) số nguyên dương ~a_{1}~, ~a_{2}~, ..., ~a_{n}~. Tổng ~a_{i}~ + ~a_{i+1}~ + ...+ ~a_{j}~ (~1 \leq i \leq j \leq N~) được gọi là tổng bộ phận từ ~i~ đến ~j~ của dãy số.

Cho hai số nguyên dương ~P~ và ~K~ (~1 < P \leq 10^{9}~, ~0 \leq K < P~). Hãy tìm tổng bộ phận theo modulo ~P~ nhỏ nhất không bé hơn ~K~.

Ví dụ, xét dãy số sau: ~[12, \, 13, \, 15, \, 11, \, 16, \, 26, \, 11]~

Ở đây ~N = 7~, giả sử ~K = 2~ và ~P = 17~, ta có kết quả là ~2~ vì ~11 + 16 + 26 = 53~ và ~53 \bmod 17 = 2~. Nếu ~K = 0~ ta có kết quả bằng ~0~ vì ~15 + 11 + 16 + 26 = 68~ và ~68 \bmod 17 = 0~.

Input

  • Dòng ~1~: ~N~, ~K~, ~P~.
  • Dòng 2 đến dòng ~N+1~: ~a_{1}~, ~a_{2}~, ..., ~a_{N}~, mỗi số trên một dòng.

Output

  • In ra tổng bộ phận theo modulo ~P~ nhỏ nhất không bé hơn ~K~.

Sample Input

7 2 17
12
13
15
11
16
26
11

Sample Output

2

Comments

Please read the guidelines before commenting.



  • 4
    CQTshadow  commented on May 22, 2021, 2:25 p.m.

    Chỗ giải thích test tự nhiên số 11 nằm trên đầu bạn cùng chăn lứa kìa ad