PROBLEM - Bài tập
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: a519Hieu zipdang2004

BéTậpĐi vừa chế được máy tính toán học gồm ba hàm đặc biệt:

Hàm thứ nhất là P(x) trả về tập hợp các ước nguyên tố của x. Ví dụ: P(15) = {3, 5}

Hàm thứ hai là factorize(x, p) trả về số nguyên pk lớn nhất sao cho x chia hết cho pk. Ví dụ: factorize(54, 3) = 27.

Hàm cuối cùng f(x, y) sẽ bằng tích của các factorize(y, p) với p thuộc tập hợp P(x). Ví dụ: f(18, 15) = factorize(15, 2) * factorize(15, 3); vì P(18) = {2, 3};

BéTậpĐi muốn viết hàm thứ tư g(x, n) = f(x, 1) * f(x, 2) * f(x, 3) * ... * f(x, n). Tuy nhiên, bé sợ máy tính chạy hàm quá lâu nên cần phải tối ưu thuật toán. Các bạn hãy giúp bé nhé!

INPUT: Gồm hai số nguyên dương duy nhất, lần lượt là x <= 10^9 và n <= 10^18.

OUTPUT: Gồm một số nguyên duy nhất là kết quả của hàm g(x, n) MOD 10^9+7

Bài có 2 subtask:

Subtask 1: x, n <= 10^4

Subtask 2: Như đề cho.

Ví dụ

INPUT OUTPUT
12 3 6

P(12) = {2, 3}

f(12, 1) = factorize(1, 2) * factorize(1, 3) = 1 * 1 = 1;

f(12, 2) = factorize(2, 2) * factorize(2, 3) = 2 * 1 = 2;

f(12, 3) = factorize(3, 2) * factorize(3, 3) = 1 * 3 = 3;

=> g(12, 3) = f(12, 1) * f(12, 2) * f(12, 3) = 1*2*3 = 6

Back to Top