Trò chơi với ổ khoá
Xem PDF
Điểm:
250
Thời gian:
5.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
An có \(n\) ổ khoá, và ban đầu tất cả ổ khoá này ở trạng thái khoá.
Vì ở nhà quá buồn chán, nên An quyến định đem \(n\) chìa khoá này ra chơi, và quá trình chơi của anh ấy diễn ra như sau:
- Trò chơi, gồm có \(n\) vòng, ở vòng thứ \(i(1\le i\le n)\), anh ấy sẽ đổi trạng thái của tất cả những ổ khoá mà chia hết cho \(i\), tức là ổ nào mở thì anh ấy khoá lại và ngược lại !
Hỏi sau khi kết thúc \(n\) vòng chơi, có bao nhiêu ổ khoá ở trạng thái mở
Input
-
Dòng thứ nhất chứa số \(t(1\le t\le 100)\) - Thể hiện số testcase
-
\(t\) dòng tiếp theo, mỗi dòng chứa số \(n(1\le n\le 100.000.000)\)
Output
- Ứng với mỗi testcase, in ra đáp án cần tìm
Scoring
- Subtask \(1\) (\(66.7\%\) số điểm): \(1\le n\le 100\)
- Subtask \(2\) (\(16.65\%\) số điểm): \(100\le n\le 5000\)
- Subtask \(3\) (\(16.65\%\) số điểm): \(5000\le n\le 100.000.000\)
Example
Test 1
Input
2
3
5Output
1
2Note
- Giả sử ta kí hiệu: \(0\)- trạng thái mở và \(1\)- trạng thái khoá.
- Xét testcase \(1\), thì quá trình chơi sẽ diễn ra như sau: \((1,1,1)\rightarrow (0,0,0) \rightarrow (0,1,0) \rightarrow (0,1,1)\) --> Do đó đáp án là \(1\)
- Xét testcase \(2\), thì quá trình chơi sẽ diễn ra như sau: \((1,1,1,1,1)\rightarrow (0,0,0,0,0)\rightarrow (0,1,0,1,0) \rightarrow (0,1,1,1,0)\rightarrow (0,1,1,0,0)\rightarrow (0,1,1,0,1)\) --> Do đó đáp án là \(2\).
Bình luận
sao đi đâu cũng thấy An hết vậy?
bởi vì tên An thường là tên đầu tiên trong danh sách:))
đúng r :))
bởi vì tên An thường là tên đầu tiên trong danh sách:))
Thì có vấn đề gì đâu, thắc mắc gì ngộ quớ 🥴🥴