VPARTSUM - Tổng bộ phận

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Cho một dãy gồm N (1 ≤ N ≤ 100000) số nguyên dương a 1 , a 2 , ..., a n . Tổng a i + a i+1 + ... + a j (1 ≤ i ≤ j ≤ 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 ≤ 10 9 , 0 ≤ 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 mod 17 = 2. Nếu K=0 ta có kết quả bằng 0 vì 15 + 11 + 16 + 26 = 68 và 68 mod 17 = 0.

Dữ liệu

  • Dòng 1: N, K, P.
  • Dòng 2..n+1: a 1 , a 2 ,... , a N , mỗi số trên một dòng.

Kết quả

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

Ví dụ

Dữ liệu
7 2 17
12
13
15
11
16
26
11

Kết quả
2


  • Người up: paulmcvn
  • Nguồn bài: Indian Computing Olympiad, Online Programming Contest, July 06