HSPC14A - Biến đổi cặp số
Giới hạn- Thời gian: 4.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Từ cặp số (a, b) gồm 2 số nguyên dương, có thể sử dụng 1 trong 3 phép biến đổi sau để tạo ra cặp số mới • • • (a,b) → (a, a+b) (a,b) → (a+b, b) (a,b) → (b,a) Bắt đầu từ cặp số (1, 1) hãy dùng ít phép biến đổi nhất để tạo ra một cặp số có chứa số N.
Từ cặp số (a, b) gồm 2 số nguyên dương, có thể sử dụng 1 trong 3 phép biến đổi sau để tạo ra
cặp số mới
(a,b) → (a, a+b)
(a,b) → (a+b, b)
(a,b) → (b,a)
Bắt đầu từ cặp số (1, 1) hãy dùng ít phép biến đổi nhất để tạo ra một cặp số có chứa số N.
Input
Dòng đầu chứa số test T. Tiếp theo là T test, mỗi test chứa một số 1 ≤ N ≤ 10^6.
Output
Ứng với mỗi test, in ra trên một dòng số bước biến đổi ít nhất.
Example
Input: 4 1 3 5 7 Output: 0 2 3 4
- Người up: beo_chay_so
- Nguồn bài: HSPC 2014