Chia Số
Xem PDFĐức rất thích cống. Nhận thấy sở thích này rất bất thường và không sạch sẽ, ami quyết định bày Đức một trò chơi liên quan đến số học.
ami cho Đức 4 số \(c,u,o,m\). Đức có thể chọn một trong 3 số \(u, o, m\) và chia \(c\) cho số được chọn. Đức có thể lặp lại thao tác trên với số lần vô hạn nếu cậu thích, mục tiêu là làm cho số \(c\) trở thành \(1\). Tuy không thích số học, nhưng lại không dám làm trái lời ami, Đức muốn nhờ các bạn tìm ra số thao tác ít nhất để biến \(c\) thành \(1\), hoặc báo cho Đức là không thể, để Đức còn có thời gian đi chơi với cống.
Input
- Dòng đầu tiên chứa \(t\) là số câu hỏi.
- \(t\) câu hỏi có dạng như sau: Dòng đầu tiên của mỗi câu hỏi chứa 1 số nguyên \(c\), dòng thứ hai chứa 3 số nguyên \(u, o, m\).
Output
- Với mỗi câu hỏi, hãy in ra số thao tác ít nhất cần dùng để biến \(c\) thành \(1\) hoặc in ra \(−1\) nếu không tồn tại bất kì cách làm nào.
Scoring
Trong tất cả các test, \(1 \leq c,u,o,m \leq 10^{18}\)
- Subtask \(1\) (\(40\%\) số điểm): \(t=1, u=o=m\)
- Subtask \(2\) (\(20\%\) số điểm): \(t \leq 100\), \(u,o,m\) đôi một nguyên tố cùng nhau
- Subtask \(3\) (\(20\%\) số điểm): \(t \leq 100, u=o\)
- Subtask \(4\) (\(20\%\) số điểm): \(t \leq 100\)
Example
Test 1
Input
3
6
1 2 3
7
1 2 7
8
4 4 4Output
2
1
-1Note
Với \(c=6,u=1,o=2,m=3\), ta có thể lấy \(6/3/2=1\) hoặc \(6/2/3=1\). Tổng cộng cần ít nhất 2 thao tác.
Với \(c=7,u=1,o=2,m=7\), ta có thể lấy \(7/7=1\). Tổng cộng cần ít nhất 1 thao tác.
Bình luận
bài này các bạn hoàn toàn có thể sử dụng đệ quy để giải bài toán theo cách đơn giản nhé :v, ai đã biết đệ quy có thể tham khảo phần đệ quy của mình :V
hehe
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.