#2737. C++-开灯问题（完全平方数）（拓展01-计算性能即计算循环次数）
-
ID: 2737
Type: Default
1000ms
256MiB
Tried: 10
Accepted: 7
Difficulty: 9
Uploaded By:
编创小匠 (paifuture)
C++-开灯问题（完全平方数）（拓展01-计算性能即计算循环次数）
Background
Description
用完全平方数来解决。
N盏灯排成一排，从1到N按顺序依次编号。有N个人也从1到N依次编号。第1个人将灯全部关闭（之前灯是开着的）。接着第2个人走过时，把凡是号码是2的倍数的灯的开关拉一下；第3个走过时，把凡是号码是3的倍数的灯的开关拉一下…
问：最后有多少盏灯关着，计算性能即计算循环次数。
Format
Input
Output
Samples
10000
1 4 9 16 25 36 49 64 81 100 121 144 169 196 225 256 289 324 361 400 441 484 529 576 625 676 729 784 841 900 961 1024 1089 1156 1225 1296 1369 1444 1521 1600 1681 1764 1849 1936 2025 2116 2209 2304 2401 2500 2601 2704 2809 2916 3025 3136 3249 3364 3481 3600 3721 3844 3969 4096 4225 4356 4489 4624 4761 4900 5041 5184 5329 5476 5625 5776 5929 6084 6241 6400 6561 6724 6889 7056 7225 7396 7569 7744 7921 8100 8281 8464 8649 8836 9025 9216 9409 9604 9801 10000
100
Limitation
1s, 1024KiB for each test case.