Phương trình Diophantine

View as PDF




Author:
Problem types
Points: 300 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

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)\).


Comments

There are no comments at the moment.