Phương trình Diophantine

Xem PDF

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

Cho ba số nguyên dương \(a, b, c\). Xét phương trình: \(a.x + b.y = c\). Hãy tìm số lượng cặp (\(x, y\)) là nghiệm của phương trình trên, với \(x, y\) là hai số nguyên dương.

Input

  • Gồm một dòng chứa ba số nguyên dương \(a, b, c \le 10^9\) cách nhau bởi dấu cách.

Output

  • Ghi ra một số nguyên duy nhất là số cặp nghiệm nguyên dương của phương trình.

Example

Test 1

Input
2 4 20
Output
4
Note

Giải thích: Trong ví dụ trên, 4 cặp nghiệm là \((2, 4), (4, 3), (6, 2)\)\((8, 1)\).


Bình luận

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