Các lượt nộp

Danh sách bài

Báo lỗi

solution

Đề bài: [An toàn thông tin] Tổng các nghịch đảo modular

Tổng nghịch đảo modular

Cho số nguyên tố $p$ và một dãy $a_1,\dots,a_k$ (mỗi $a_i$ không chia hết cho $p$ ). Hãy tính:

$\left(\sum_{i=1}^{k} a_i^{-1}\right) \bmod p$

trong đó $a_i^{-1}$ là nghịch đảo modular của $a_i$ theo Fermat.

Ví dụ

$p=7$ , dãy $\{2,3\}$ : $2^{-1}=4$ , $3^{-1}=5$ , tổng $=9\equiv2\pmod7$ .

Định dạng đầu vào:
Dòng đầu là $p$ . Dòng sau là $k$ rồi $k$ số $a_1,\dots,a_k$ .
Ràng buộc đầu vào:
$p$ nguyên tố, $2 \le p < 10^{9}$ , $1 \le k \le 10^{5}$ , $1 \le a_i < p$ .
Định dạng đầu ra:
Một số nguyên là tổng các nghịch đảo modulo $p$ .

Ví dụ:

Đầu vào:

7
2 2 3

Đầu ra:

2

Giải thích:

2^{-1}=4, 3^{-1}=5, tổng 9 ≡ 2 (mod 7).

Đang tải editor...