{"problem":{"name":"C. Divide","description":{"content":"Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ _Blockchain_. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10227C"},"statements":[{"statement_type":"Markdown","content":"Đằng sau sự thành công của Bitcoin, không thể không kể đến công nghệ _Blockchain_. Blockchain hoạt động dựa trên các khối liên kết với nhau tạo thành một chuỗi. Điều đặc biệt ở đây chính là blockchain có độ bảo mật rất cao, không thể thay đổi.\n\nHacker b21 đã gây chấn động toàn cầu khi đã tìm ra cách hack được Blockchain. Anh đã mã hóa toàn bộ các block trở thành một số N. Số N này phải thỏa mãn điều kiện sau:\n\n- Là một số tự nhiên.\n\n- Chia hết cho x.\n\n- thuộc khoảng [A, B].\n\n- UCLN của chữ số thứ i tính từ phải qua trái và i phải bằng 1. (Ví dụ: 321 không thỏa mãn vì UCLN(1, 1) = 1, UCLN(2, 2) = 2, UCLN(3, 3) = 3 nhưng 231 thỏa mãn vì UCLN(1, 1) = 1, UCLN(3, 2) = 1, UCLN(2, 3) = 1) .\n\n- Bao gồm các chữ số cho trước\n\nCác bạn hãy giúp b21 tìm ra số lượng các số như thế nhé.\n\nDòng đầu tiên chứa ba số nguyên A, B, X.\n\nDòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N\n\nChứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 109 + 7\n\nB ≤ A\n\n10% số test ứng với A, B, X ≤ 103\n\n30% số test ứng với A, B ≤ 106, X ≤ 105\n\n30% số test ứng với A, B, X ≤ 1011\n\n30% số test ứng với A, B ≤ 10100, X ≤ 105\n\nGiải thích test 1: 2, 4, 8, 12, 14, 18\n\nGiải thích test 2: 3, 6, 12, 18\n\n## Input\n\nDòng đầu tiên chứa ba số nguyên A, B, X.Dòng thứ hai có xâu S chứa các chữ số 0..9 theo thứ tự tăng dần là các số có trong N\n\n## Output\n\nChứa duy nhất 1 số nguyên là phần dư của phép chia kết quả bài toán cho 109 + 7\n\n[samples]\n\n## Scoring\n\nB ≤ A10% số test ứng với A, B, X ≤ 10330% số test ứng với A, B ≤ 106, X ≤ 10530% số test ứng với A, B, X ≤ 101130% số test ứng với A, B ≤ 10100, X ≤ 105\n\n## Note\n\nGiải thích test 1: 2, 4, 8, 12, 14, 18Giải thích test 2: 3, 6, 12, 18","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, P, Q \\in \\mathbb{Z} $ with $ 1 \\le n \\le 2000 $, $ 0 \\le P, Q \\le 10^5 $.  \nLet $ X = \\{x_1, x_2, \\dots, x_n\\} \\subset \\mathbb{Z} $ be the set of bomb locations, with $ 1 \\le x_i \\le 10^9 $, all distinct.  \n\n**Constraints**  \n- Use at most $ P $ type-1 tools, each covering a segment of length $ w $.  \n- Use at most $ Q $ type-2 tools, each covering a segment of length $ 2w $.  \n- Each tool covers a contiguous subsegment of the real line $[1, 10^9]$.  \n- A tool destroys all bombs lying within its covered segment.  \n- Each tool may be used at most once.  \n\n**Objective**  \nFind the minimum $ w \\in \\mathbb{Z}^+ $ such that all bombs in $ X $ can be covered by a combination of at most $ P $ type-1 intervals of length $ w $ and at most $ Q $ type-2 intervals of length $ 2w $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10227C","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}