VPARTSUM - Tổng bộ phận

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

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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