Bài tập | NEU OJ

Căn nguyên thủy nhỏ nhất

Cho số nguyên tố $p$ . Căn nguyên thủy $g$ là số mà cấp của nó bằng $p-1$ , tức các lũy thừa $g^1, g^2, \dots, g^{p-1}$ sinh ra toàn bộ $\{1,\dots,p-1\}$ modulo $p$ .

Hãy tìm căn nguyên thủy nhỏ nhất $g \ge 1$ . (Quy ước: với $p=2$ căn nguyên thủy là $1$ .)

Ví dụ

Với $p=7$ , căn nguyên thủy nhỏ nhất là $3$ .

Định dạng đầu vào:
Một số nguyên tố $p$ .
Ràng buộc đầu vào:
$2 \le p \le 10^{9}$ , $p$ nguyên tố.
Định dạng đầu ra:
Căn nguyên thủy nhỏ nhất modulo $p$ .

solution

Đề bài: [Toán cho CNTT] Căn nguyên thủy modulo p

Căn nguyên thủy nhỏ nhất

Ví dụ