Phương trình đồng dư tuyến tính một ẩn

Xem PDF

Điểm: 300 (p) Thời gian: 1.0s Bộ nhớ: 64M Input: bàn phím Output: màn hình

Cho phương trình đồng dư: \(a.x ≡ b (\mod ⁡m)\), với \(a, b, m\) là các số nguyên, \(m > 0\)\(x\) là số nguyên chưa biết (ẩn số), gọi là phương trình đồng dư tuyến tính một ẩn.

Bạn hãy tìm tất cả các nghiệm nguyên không âm nhỏ nhất và không đồng dư với nhau theo modun \(m\) của phương trình trên.

Input

  • Gồm một dòng chứa ba số nguyên \(a, b, m\) (\(-10^9 \le a, b \le 10^9, 0 < m \le 10^9\)).

Dữ liệu vào đảm bảo có không quá \(10^5\) nghiệm cần tìm.

Output

  • Dòng đầu tiên ghi ra số nghiệm nguyên không âm nhỏ nhất và không đồng dư với nhau theo modun \(m\).
  • Mỗi dòng tiếp theo ghi ra một nghiệm tìm được theo thứ tự tăng dần.

Example

Test 1

Input
9 12 15
Output
3
3
8
13

Test 2

Input
15 -24 50
Output
0

Bình luận

Không có bình luận nào.