trang chủ / đề bài / icpc26_mb_j

Ma trận lưu trữ

Đề bài

Mô tả

Sâu bên dưới Khu vực 2026, trưởng đoàn thám hiểm Niko đến được lối vào Tháp Lõi Trung tâm để khôi phục ma trận sao của hành tinh. Các cánh cửa chống nổ an ninh chính bị khóa bằng một bàn phím lượng tử do thực thể trí tuệ nhân tạo cổ xưa mang tên The World Machine để lại.

Bên cạnh bàn phím là lối vào một kho lưu trữ dữ liệu vô hạn, gồm vô hạn đếm được các giá lưu trữ được đánh số 1,2,3,… và vô hạn các cuốn dữ liệu (codex) có tiêu đề 1,2,3,…. Mỗi cuốn i chứa đúng một số nguyên dương ai.

Kho lưu trữ tuân theo các quy tắc cân bằng tự tham chiếu nghiêm ngặt:

  1. Cuốn i được xếp lên giá ai.
  2. Tổng số cuốn được xếp lên giá i đúng bằng ai.
  3. Cuốn 1 chứa giá trị 1 (tức là a1=1).
  4. Các giá trị không giảm: nếu i<j thì ai≤aj (điều này xác định duy nhất dãy ai, được gọi là dãy Golomb).

Màn hình an ninh hiện dòng chữ: mật mã mở khóa là tổng các số được ghi bên trong tất cả các cuốn có tiêu đề từ 1 đến N, lấy phần dư khi chia cho M. Hãy giúp Niko tính mật mã cửa.

Trong đề thi gốc, dữ liệu vào cố định là N=1018 và M=12345678987654321; ở đây N và M được cho trong dữ liệu vào (cặp giá trị gốc là một trong các test).

Dữ liệu vào

Một dòng gồm hai số nguyên N và M cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên: mật mã mở khóa, tức là (a1+a2+…+aN)modM.

Ràng buộc

  • 1≤N≤1018
  • 1≤M≤1018

Ví dụ

Input Output Giải thích
10 1000 33 Mười số hạng đầu của dãy Golomb là 1,2,2,3,3,4,4,4,5,5, tổng bằng 33.
100 999 289 Tổng 100 số hạng đầu bằng 1288, và 1288mod999=289.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0