Số lưỡng phân
Đề bài
Mô tả
Ban giám đốc công ty nơi bạn làm việc muốn gửi cho nhau các thông điệp được mã hoá. Thay vì dùng phần mềm mã hoá có sẵn như PGP, họ giao cho bộ phận IT tự giải quyết việc mã hoá. Bộ phận IT chọn một cách làm cần các khoá số nguyên "công khai" và "bí mật". Ý tưởng là ai cũng thấy khoá công khai của bạn, nhưng chỉ bạn biết khoá bí mật của mình.
Người bạn thân nhất của bạn trong công ty là một người tuyệt vời nhưng là một lập trình viên không mấy tuyệt vời. Anh ấy đã tạo ra một cơ chế khoá công khai, bí mật như sau. Khoá công khai có thể là một số nguyên dương bất kỳ. Khoá bí mật tương ứng là số lưỡng phân nhỏ nhất lớn hơn khoá công khai và là bội của khoá công khai.
Một số lưỡng phân là một số nguyên dương có đúng chữ số thập phân khác nhau và sao cho và mọi lần xuất hiện của đều đứng trước mọi lần xuất hiện của . Ví dụ là số lưỡng phân ( là và là ), các số , và cũng vậy. Tuy nhiên, cả lẫn đều không phải số lưỡng phân.
Để ý rằng số lưỡng phân lớn có thể mô tả gọn là chữ số theo sau bởi chữ số . Mọi số lưỡng phân đều có thể biểu diễn bằng bốn số : và là chữ số đứng đầu và chữ số đứng cuối như trên, là số lần chữ số xuất hiện trong số lưỡng phân, và là số lần chữ số xuất hiện.
Vấn đề của cơ chế này là tính khoá bí mật từ khoá công khai không quá khó. Bạn cần thuyết phục người bạn rằng cơ chế của anh ấy không an toàn trước khi anh ấy mất việc vì quyết định tồi này! Hãy viết chương trình nhận vào các khoá công khai và in ra khoá bí mật tương ứng.
Dữ liệu vào
Dữ liệu gồm nhiều bộ test. Mỗi bộ test nằm trên một dòng riêng, gồm một khoá công khai duy nhất là số nguyên trong khoảng từ đến .
Sau bộ test cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bộ test, in một dòng gồm khoá công khai, một dấu hai chấm, rồi số nguyên như mô tả ở trên (định dạng như ví dụ).
Ràng buộc
- Mỗi khoá công khai là số nguyên từ đến .
- Mỗi file có từ đến khoá công khai (không tính dòng cuối cùng).
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 125 17502 2005 0 |
125: 1 5 2 0 17502: 4 7 4 8 2005: 3 2 3 5 |
Khoá bí mật lần lượt là , và . |
| 10 1 41 99999 0 |
10: 1 2 1 0 1: 1 1 1 0 41: 1 8 1 2 99999: 5 9 1 0 |
Ví dụ tự thêm. là số lưỡng phân nhưng khoá bí mật phải lớn hơn hẳn khoá công khai, nên đáp án là . Với khoá , đáp án là (số đến chỉ có một chữ số khác nhau). Khoá cho , khoá cho . |
Bình luận