原题
题目描述
正整数 $ N $ に対し、$ N $ が 400 number であることは以下の $ 2 $ つの条件をともに満たすことであると定義します。
- $ N $ の素因数はちょうど $ 2 $ 種類である。
- $ N $ の各素因数 $ p $ について、$ N $ が $ p $ で割り切れる回数は偶数回である。より厳密には、$ N $ の各素因数 $ p $ について $ p^k $ が $ N $ の約数であるような最大の非負整数 $ k $ は偶数である。
$ Q $ 個のクエリが与えられるので、それぞれについて答えてください。各クエリでは、整数 $ A $ が与えられるので、$ A $ 以下の最大の 400 number の値を求めてください。ただし、本問題の制約下では $ A $ 以下の 400 number は常に存在します。
输入格式
入力は以下の形式で標準入力から与えられる。
$ Q $ $ \text{query}_1 $ $ \text{query}_2 $ $ \vdots $ $ \text{query}_Q $
ここで、$ \text{query}_i $ は $ i $ 番目のクエリであり、以下の形式で与えられる。
$ A $
输出格式
$ Q $ 行出力せよ。$ i $ 行目には $ i $ 番目のクエリに対する答えを出力せよ。
输入输出样例 #1
输入 #1
5
404
36
60
1000000000000
123456789
输出 #1
400
36
36
1000000000000
123454321
说明/提示
制約
- $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $
- 各クエリについて、$ 36\ \leq\ A\ \leq\ 10^{12} $
- 入力される値はすべて整数
Sample Explanation 1
$ 1 $ 番目のクエリについて説明します。 $ 400 $ の素因数は $ 2,\ 5 $ のちょうど $ 2 $ 種類であり、$ 400 $ が $ 2 $ で割り切れる回数は $ 4 $ 回、$ 5 $ で割り切れる回数は $ 2 $ 回であるため $ 400 $ は 400 number です。$ 401,\ 402,\ 403,\ 404 $ は 400 number ではないため答えは $ 400 $ となります。
思路
分析
首先发现它是有多个询问，如果每个询问都去单独处理，很明显十分耗时间。所以预处理是个好东西，将所有数处理出来后再进行二分。
但是 A ≤ 1 0 12 A \le 10^{12} A≤1012 该怎么办呢?可以发现它的要求是有两个质因子，且次数为偶数，那么肯定是一个平方数。那 1 0 12 10^{12} 1012 以内肯定最多有 1 0 6