Bài tập | NEU OJ

Giải $ax \equiv b \pmod n$

Phương trình đồng dư tuyến tính $ax\equiv b\pmod n$ có nghiệm khi và chỉ khi $g=\gcd(a,n)$ chia hết $b$ . Khi đó có đúng $g$ nghiệm phân biệt modulo $n$ .

Cho $a$ , $b$ , $n$ :

Nếu vô nghiệm, in $-1$ .
Nếu có nghiệm, in số nghiệm $g$ trên dòng đầu; dòng thứ hai in $g$ nghiệm tăng dần trong $[0,n)$ , cách nhau bởi dấu cách.

Ví dụ

$6x\equiv 4\pmod 8$ có $g=\gcd(6,8)=2$ chia hết $4$ , hai nghiệm là $2$ và $6$ .

Định dạng đầu vào:
Một dòng gồm ba số nguyên $a$ , $b$ , $n$ .
Ràng buộc đầu vào:
$1 \le a < 10^{9}$ , $0 \le b < 10^{9}$ , $2 \le n < 10^{9}$ .
Định dạng đầu ra:
Hoặc $-1$ (vô nghiệm), hoặc dòng đầu là số nghiệm $g$ , dòng sau là $g$ nghiệm tăng dần.

solution

Đề bài: [An toàn thông tin] Giải phương trình đồng dư tuyến tính

Giải $ax \equiv b \pmod n$

Ví dụ

solution

Đề bài: [An toàn thông tin] Giải phương trình đồng dư tuyến tính

Giải ax≡b(modn)ax \equiv b \pmod nax≡b(modn)

Ví dụ

Giải $ax \equiv b \pmod n$