Cho hàm số f (a, b):
Với gcd(a, b) là ước chung lớn nhất của a và b.
Yêu cầu: Cho hai số tự nhiên x và y. Yêu cầu tính f(x, y).
Dữ liệu: Một dòng duy nhất chứa hai số tự nhiên x và y (1 ≤ x, y ≤ 1012).
Kết quả: Một số duy nhất là kết quả của f(x, y).
Ví dụ
|
INPUT |
OUTPUT |
|
4 9 |
3 |
|
6 17 |
5 |
Giải thích:
- Test 1:
f(4, 9) = 1 + f(4, 9 – gcd(4, 9)) = 1 + f(4, 8);
<=> f(4, 9) = 1 + 1 + f(4, 8 - gcd(4, 8)) = 2 + f(4, 4);
<=> f(4, 9) = 2 + 1 + f(4, 4 - gcd(4, 4)) = 3 + f(4, 0) = 3.
- Test 2:
f(6, 17) = 1 + f(6, 17- gcd(6, 17)) = 1 + f(6, 16);
<=> f(6, 17) = 1 + 1 + f(6,16 - gcd(6, 16)) = 2 + f(6, 14);
<=> f(6, 17) = 2 + 1 + f(6, 14 - gcd(6, 14)) = 3 + f(6, 12);
<=> f(6, 17) = 3 + 1 + f(6, 12 - gcd(6, 12)) = 4 + f(6, 6);
<=> f(6, 17) = 4 + 1 + f(6, 6 - gcd(6, 6)) = 5 + f(6, 0) = 5.
Giới hạn:
- Subtask 1 (25% số test): 1 ≤ x, y ≤ 106;
- Subtask 2 (75% số test): Không có ràng buộc gì thêm.