Vàng suy giảm của nhà giả kim
Đề bài
Mô tả
Một nhà giả kim đã tạo ra một khối vàng ma thuật có Giá trị tinh chất ban đầu là . Ông dự định thực hiện quá trình tinh luyện đúng lần để làm tinh khiết nó.
Mỗi lần quá trình được thực hiện trên một khối vàng có Giá trị tinh chất , khối vàng vỡ thành nhiều mảnh. Giá trị tinh chất của các mảnh này đúng bằng các ước của . Do tính hỗn loạn của phản ứng ma thuật, nhà giả kim phải chọn ngẫu nhiên một trong các mảnh để tiếp tục quá trình. Mọi mảnh (tức là mọi ước) đều có khả năng được chọn như nhau.
Nhà giả kim muốn dự đoán kết quả thí nghiệm của mình. Giá trị tinh chất kỳ vọng của khối vàng cuối cùng sau bước tinh luyện là bao nhiêu?
Đáp án có thể biểu diễn dưới dạng phân số , trong đó và nguyên tố cùng nhau và . Hãy in ra .
Dữ liệu vào
Một dòng duy nhất chứa hai số nguyên và (, ).
Dữ liệu ra
In ra một số nguyên: Giá trị tinh chất kỳ vọng sau bước tinh luyện, theo modulo .
Ràng buộc
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 7 1 | 4 | Các ước của là và , kỳ vọng là . |
| 7 3 | 750000007 | Sau bước, khối vàng còn giá trị với xác suất , nên kỳ vọng là . Khi đó . |
| 77 7 | 642333990 | . |
Bình luận