trang chủ / đề bài / icpc25_mn_d

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à n. Ông dự định thực hiện quá trình tinh luyện đúng k 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 v, 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 v. 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 k bước tinh luyện là bao nhiêu?

Đáp án có thể biểu diễn dưới dạng phân số PQ, trong đó P và Q nguyên tố cùng nhau và Q≢0(mod109+7). Hãy in ra P·Q−1mod(109+7).

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên n và k (1≤n≤1015, 1≤k≤104).

Dữ liệu ra

In ra một số nguyên: Giá trị tinh chất kỳ vọng sau k bước tinh luyện, theo modulo 109+7.

Ràng buộc

  • 1≤n≤1015
  • 1≤k≤104

Ví dụ

Input Output Giải thích
7 1 4 Các ước của 7 là 1 và 7, kỳ vọng là 1+72=4.
7 3 750000007 Sau 3 bước, khối vàng còn giá trị 7 với xác suất 18, nên kỳ vọng là 18·7+78·1=74. Khi đó 7·4−1≡750000007(mod109+7).
77 7 642333990 77=7·11.

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