TLE-oj Cup Round 8 - Gcd về 0
Xem PDF
Nộp bài
Điểm:
1300 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
128M
Input:
GCDTOZERO.inp
Output:
GCDTOZERO.out
Tác giả:
Dạng bài
Bạn được cho 2 số n và m. Mỗi bước bạn được trừ n cho ước chung lớn nhất của n và m. Nhiệm vụ của bạn là đếm số bước để đưa n về 0
Input, Output và Subtasks
Input: (GCDTOZERO.inp)
- Dòng đầu tiên gồm 2 số n và m (n\le 10^{18},m\le 10^{16})
Output: (GCDTOZERO.out)
- Một số duy nhất là kết quả của bài toán
Subtasks
- Subtask 1 (10\%): n\le 10^6.
- Subtask 2 (10\%): n\le 10^8.
- Subtask 3 (10\%): n\le 10^{10}.
- Subtask 4 (15\%): n\le 10^{12}.
- Subtask 5 (15\%): n\le 10^{14}.
- Subtask 6 (15\%): n\le 10^{16}.
- Subtask 7 (25\%): Không có ràng buộc gì thêm
Sample
Input (GCDTOZERO.inp)
10 3
Output (GCDTOZERO.out)
4
Bình luận