Trò chơi với ổ khoá

Xem PDF
Tác giả:
jumptozero
Dạng bài
Ngôn ngữ cho phép
C#, C++, Clang, Clang++, Cobol, D, Groovy, Haskell, Java, JS, Kotlin, Lua, Node JS, ObjectiveC, OCaml, Output, PHP, Prolog, Pypy, Pypy 3, Ruby, Rust, Scala, Scratch, Swift
Đ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
5
Output 
1
2
Note
  • 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