分数: 425 点
问题陈述
正整数 N 是 400号 当且仅当满足以下两个条件:
- N 正是 2 不同的质因数。
- 对于每个质因数 p of N, p 划分 N 偶数次。更正式地说,最大非负整数 k 这样 p^k 划分 N 是偶数。
流程 Q 查询。每个查询都会给你一个整数 A,所以找到最大不超过400的数 A。在这个问题的约束下,400个数不超过 A 始终存在。
约束
- 1 \leq Q \leq 2 \times 10^5
- 对于每个查询, 36 \leq A \leq 10^{12}.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, \text{query}_i 是 i-第一个查询,按以下格式给出:
A
输出
打印 Q 行。的 i- 第行应包含以下问题的答案 i第一个查询。
示例输入 1
5 404 36 60 1000000000000 123456789
示例输出 1
400 36 36 1000000000000 123454321
让我们解释一下第一个查询。
正好有 2 的质因数 400: 2 和 5。另外, 2 划分 400 四次并且 5 将其除两次,所以 400 是一个 400 号码。没有一个 401, 402, 403,和 404 是一个 400 数字,所以答案是 400.