Số học mô-đun

Điểm: 6,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Assembly, C#, C++, D, Dart, Go, Groovy, Java, Javascript, Kotlin, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Ruby, Rust, Scratch, Typescript, Zig

Cho hai số nguyên cố định $k$ và $p$ , trong đó $p$ là một số nguyên tố lẻ. Xét phương trình hàm sau đối với hàm số $f : {0, 1, \dots, p - 1} \to {0, 1, \dots, p - 1}$ :

$k \cdot f (x) \equiv f (k \cdot x mod p) (\mod p)$

Phương trình trên phải đúng với mọi số nguyên $x$ trong khoảng từ $0$ đến $p - 1$ .

Hãy đếm số hàm $f$ phân biệt thỏa mãn phương trình trên. Vì kết quả có thể rất lớn, hãy in ra phần dư của nó khi chia cho $10^{9} + 7$ .

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $p$ và $k$ cách nhau bởi dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất — số hàm $f$ phân biệt thỏa mãn phương trình, lấy phần dư cho $10^{9} + 7$ .

Ràng buộc

$3 \leq p \leq 10^{6}$
$0 \leq k \leq p - 1$
$p$ là số nguyên tố lẻ.

Ví dụ

Input	Output	Giải thích
3 2	3	Ba hàm thỏa mãn: $f (0) = 0, f (1) = 1, f (2) = 2$ ; $f (0) = 0, f (1) = 2, f (2) = 1$ ; $f (0) = f (1) = f (2) = 0$ .
5 4	25	Có $25$ hàm thỏa mãn ứng với $p = 5, k = 4$ .
5 0	625	Khi $k = 0$ , phương trình chỉ ép $f (0) = 0$ ; bốn giá trị còn lại của $f$ tự do, cho $5^{4} = 625$ hàm.

Bình luận

Không có bình luận tại thời điểm này.