幻想中成为原神

Luogu
IDLGP8883
Time2000ms
Memory512MB
DifficultyP5
数学Special JudgeO2优化
其中一个问题是这样的:定义一个丘丘人是可以被击杀的,当且仅当存在一个大于 $1$ 的完全平方数能够整除它的编号。比如,$12$ 号丘丘人就是可以被击杀的,因为它能够被 $4$ 整除;$15$ 号丘丘人则不能被击杀。请计算编号为 $1\sim n$ 中的丘丘人中能够被击杀的个数。由于钟离秉承着“差不多得了”的做事理念,因此,他允许你的答案与真正的答案有着不超过 $2\times10^4$ 的绝对误差。 ## Input **本题多组询问**。第一行输入一个数 $T$,表示询问组数。 每组询问输入一行,一个正整数 $n$。 ## Output 对于每组询问,输出一行一个整数,表示编号为 $1\sim n$ 中的丘丘人中能够被击杀的个数。 [samples] ## Background 钟离很喜欢数学题。 ## Note #### 样例解释 $1\sim 10$ 中,只有 $4,8,9$ 这 $3$ 个丘丘人可以被击杀,因此答案为 $3$。 需要注意的是,由于你的答案被允许与标准答案有 $2\times 10^4$ 的绝对误差,因此 $-2,3,20003$ 等输出都将被认为是正确的。 #### 数据范围 - $\text{Subtask 1(10 pts)}$:$n\le 10^5$。 - $\text{Subtask 2(20 pts)}$:$n\le 10^7$。 - $\text{Subtask 3(20 pts)}$:$n\le 10^9$。 - $\text{Subtask 4(20 pts)}$:$T=1$。 - $\text{Subtask 5(30 pts)}$:无特殊性质。 对于 $100\%$ 数据,满足 $1\le n\le 10^{18}$,$1\le T\le 10^4$,保证 $n$ 在范围内随机得到。
Samples
Input #1
3
10
32678
9686985
Output #1
3
12814
3797988
API Response (JSON)
{
  "problem": {
    "name": "幻想中成为原神",
    "description": {
      "content": "其中一个问题是这样的:定义一个丘丘人是可以被击杀的,当且仅当存在一个大于 $1$ 的完全平方数能够整除它的编号。比如,$12$ 号丘丘人就是可以被击杀的,因为它能够被 $4$ 整除;$15$ 号丘丘人则不能被击杀。请计算编号为 $1\\sim n$ 中的丘丘人中能够被击杀的个数。由于钟离秉承着“差不多得了”的做事理念,因此,他允许你的答案与真正的答案有着不超过 $2\\times10^4$ 的绝对误差",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8883"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "其中一个问题是这样的:定义一个丘丘人是可以被击杀的,当且仅当存在一个大于 $1$ 的完全平方数能够整除它的编号。比如,$12$ 号丘丘人就是可以被击杀的,因为它能够被 $4$ 整除;$15$ 号丘丘人则不能被击杀。请计算编号为 $1\\sim n$ 中的丘丘人中能够被击杀的个数。由于钟离秉承着“差不多得了”的做事理念,因此,他允许你的答案与真正的答案有着不超过 $2\\times10^4$ 的绝对误差...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments