TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1661
  • 题目
  • P1661【秋分欢乐赛】汪星人入侵
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    Rainbow的城堡有N扇门,从1到N标号,它们初始时都是关着的。现在来了N只汪星人,第i只汪星人会把所有标号能被i整除的门的状态改变(即把标号能被i整除的关着的门打开,把标号能被i整除的开着的门关上)。
    Rainbow为城堡定义了一个不安全指数——即最后打开着的门的数目。Rainbow想请你帮忙计算,城堡的不安全指数是多少?

    输入格式

    每个测试点包括多组测试数据。
    第一行一个整数T,表示一共有T组测试数据。
    接下来T行每行一个整数N,表示Rainbow城堡的门的数量。

    输出格式

    输出T行,第i行的数字表示,对于第i个N,城堡的不安全指数。

    样例输入

    4
    4
    10
    16
    27

    样例输出

    2
    3
    4
    5

    提示

    样例解释:   
    当N=4的时候,4扇门情况如下(1表示开,0表示关):
    没有汪星人来的时候:0000
    第一只汪星人来后:1111
    第二只汪星人来后:1010
    第三只汪星人来后:1000
    第四只汪星人来后:1001
    所以答案为2
    对于20%的数据,T<=100.
    对于100%的数据,T<=20000,N<=50000.



    来源  来自Clover&Poetize秋分欢乐赛