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

    solution

    Đề bài: [Toán cho CNTT] Giải phương trình đồng dư tuyến tính

    Giải đồng dư tuyến tính ax≡b(modm)ax \equiv b \pmod max≡b(modm)

    Cho aaa, bbb, mmm. Tìm tất cả nghiệm xxx trong [0,m−1][0, m-1][0,m−1] của: ax≡b(modm).a x \equiv b \pmod m.ax≡b(modm).

    Đặt d=gcd⁡(a,m)d=\gcd(a,m)d=gcd(a,m). Nghiệm tồn tại ⇔d∣b\Leftrightarrow d \mid b⇔d∣b, khi đó có đúng ddd nghiệm. Nếu vô nghiệm, in -1.

    Ví dụ

    6x≡8(mod14)6x \equiv 8 \pmod{14}6x≡8(mod14): d=2∣8d=2 \mid 8d=2∣8, hai nghiệm x=6,13x=6, 13x=6,13.

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

      Một dòng gồm ba số nguyên aaa, bbb, mmm.

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

      1≤a≤1091 \le a \le 10^{9}1≤a≤109, 0≤b≤1090 \le b \le 10^{9}0≤b≤109, 2≤m≤1062 \le m \le 10^{6}2≤m≤106.

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

      Dòng đầu là số nghiệm; nếu >0>0>0, dòng sau là các nghiệm tăng dần cách nhau dấu cách. Nếu vô nghiệm in -1.

    Ví dụ:

    Đầu vào:

    6 8 14

    Đầu ra:

    2
6 13

    Giải thích:

    d=gcd(6,14)=2 chia het 8; nghiem 6 va 13.

    Đang tải editor...