Teemo Hái Nấm
Teemo có một cánh đồng nấm gồm N*N ô. Các dòng được đánh số từ 1 đến N từ trên xuống dưới, các cột được đánh số từ 1 đến N từ trái sang phải. Teemo rất thích ma trận hình xoắn ốc vì vậy anh ta đã đánh số các ô nấm của mình theo số thứ tự xoắn ốc bắt đầu từ ô \((1, 1)\) . Hình xoắn ốc đi từ ngoài vào trong theo chiều kim đồng hồ.
Hình dưới là ví dụ với bảng \(N = 5.\)
Rồi mùa thu hoạch nấm đã tới, Teemo đang ở vị trí của ô số \(X\) và muốn chuyển đến ô của số \(Y\) bằng cách thực hiện một số bước di chuyển. Trong mỗi bước, Teemo chỉ có thể di chuyển từ ô số A đến ô số B nếu:
- Ô chứa số \(A\) và ô chứa số \(B\) có chung một cạnh.
- \(A\) và \(B\) nguyên tố cùng nhau.
Cho \(N, X, Y\) , Teemo muốn biết số bước di chuyển ít nhất để chuyển từ ô số X đến ô số Y. Các bạn hãy giúp anh ấy nhé.
Dữ liệu nhập:
- Dòng đầu tiên chứa số nguyên T là số lượng test. \((1 ≤ T ≤ 10)\)
- Trong T dòng tiếp theo, mỗi test trên một dòng là 03 số nguyên N, X và Y \((1 ≤ N ≤ 1000 , 1 ≤ X, Y ≤ 10^6) \).
Dữ liệu xuất:
- Với mỗi test, in ra số bước ít nhất để di chuyển từ ô số X đến ô số Y. Nếu không di chuyển được in ra -1
Ví dụ
Input:
1
5 3 18
Output:
3
Thực hiện 3 bước:
- Từ ô số 3 chuyển qua ô số 4 (3 và 4 nguyên tố cùng nhau)
- Từ ô số 4 chuyển qua ô số 19 (4 và 19 nguyên tố cùng nhau)
- Từ ô số 19 chuyển qua ô số 18 (19 và 18 nguyên tố cùng nhau)
Comments
vậy theo input thì teemo đi từ ô 3 sang ô 25 rồi quay lại 18 thì chỉ có 2 bước chứ nhỉ
ai cho em xin ảnh ma trận kia được không ạ:<
chắc là như thế này :D
spiral-matrix.png
XIn lỗi các bạn. Cập nhật lại N <= 1000 nhé