400 number であるための \(2\) つ目の条件は \(N\) が平方数であることと同値です。

\(10^{12}\) 以下の平方数は \(10^6\) 個しかないため、それぞれについて 400 number であるか判定し、400 number を列挙することを目指します。

\(k\) の素因数の集合と \(k^2\) の素因数の集合は一致するため、\(k = 1, 2, \ldots, 10^6\) に対して素因数の種類数が求まれば 400 number をすべて列挙することができます。

\(k = 1, 2, \ldots, 10^6\) に対する素因数の種類数はエラトステネスの篩と同様の原理によって求めることができます。具体的には、数列 \(V = (V_1, V_2, \ldots, V_{10^6})\) を \(0\) で初期化しておき、\(10^6\) 以下の各素数 \(p\) について、すべての \(p\) の倍数 \(i\) に対し \(V_i\) に \(1\) を加算する操作を行うと最終的な \(V_i\) の値が \(i\) の素因数の種類数となります。

\(10^{12}\) 以下の 400 number がすべて列挙できれば 400 number をソートした列に対して二分探索を行うことで \(A\) 以下の最大の 400 number を求めることができます。

なお、\(10^{12}\) 以下の 400 number の個数は全部で \(288726\) 個です（実行時間制限に間に合う確信をもつためには \(10^6\) 以下であることさえ分かっていれば十分です）。

実装例

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	int A = 1000001;
	vector<int> v(A);
	for (int i = 2; i < A; i++) {
		if (v[i] == 0) for (int j = i; j < A; j += i) v[j]++;
	}
	vector<ll> vec;
	for (ll i = 2; i < A; i++) if (v[i] == 2) vec.push_back(i * i);
	int q;
	cin >> q;
	while (q--) {
		ll a;
		cin >> a;
		cout << *prev(upper_bound(vec.begin(), vec.end(), a)) << '\n';
	}
}