Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Nghịch đảo modular

    Cho hai số nguyên aaa và mmm với gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1. Hãy tìm nghịch đảo modular xxx của aaa theo modulo mmm — tức a⋅x≡1(modm)a \cdot x \equiv 1 \pmod{m}a⋅x≡1(modm), với 0≤x<m0 \le x < m0≤x<m. (Dùng thuật toán Euclid mở rộng.)

    • Định dạng đầu vào:

      Một dòng chứa hai số nguyên aaa và mmm.

    • Ràng buộc đầu vào:

      1≤a<m≤10121 \le a < m \le 10^{12}1≤a<m≤1012, đảm bảo gcd⁡(a,m)=1\gcd(a, m) = 1gcd(a,m)=1.

    • Định dạng đầu ra:

      In nghịch đảo modular của aaa theo mmm.

    Ví dụ:

    Đầu vào:

    3 11

    Đầu ra:

    4

    Giải thích:

    3*4 = 12 ≡ 1 (mod 11) nên nghịch đảo của 3 là 4.

    Đang tải editor...