1000ms

Difficulty: 4

所属公司 : 小红书

时间 :2025年8月20日

算法与标签>数学

会员或题库专享

请先，开通会员或购买题库小红书机考编程题库，可解锁完整内容。

购买小红书机考编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（小红书机考编程题库），可解锁完整内容。

购买题库开通会员

解题思路

预处理素数
- 利用埃氏筛在线性或近线性时间求出所有不超过 $\sqrt{10^9}\approx31623$ 的素数，记作列表 $P$
分解与累加 对每个查询的 $n$ ：

题目内容

小红薯定义一个点赞数 $n$ 为好数，当且仅当这个数的所有本质不同质因子之和为奇数。

例如， $12$ 的本质不同质因子为{ $2，3$ }，且 $2+3=5$ 为奇数，因此 $12$ 是好数。