AtCoder Beginner Contest 400, E : Ringo's Favorite Numbers 3

問題文

　https://atcoder.jp/contests/abc400/tasks/abc400_e

問題概要

　以下の問いに $q$ 回答えよ：

• 正整数 $a$ が与えられる．$a$ 以下の正整数 $n \in \mathbb Z_{ {} > 0 }$ であって，以下の条件を満たすものの内で最大のものを求めよ：
  • $n$ の素因数はちょうど $2$ 種類である．
  • $n$ を素因数分解したとき，各素因数の指数は全て偶数である．

制約

• $1 \leq q \leq 2 \times 10^5$
• $36 \leq a \leq 10^{ 12 }$ (for each query)

解法

　$n$ を素因数分解したときの各素因数の指数が偶数ということは，各素因数の指数を半分にする（i.e., $\frac 1 2$ 倍にする）操作が可能ということです．指数を半分にするというのは言い換えれば平方根をとるということなので，逆に，条件を満たす数は平方数です．$2$ 乗する操作は素因数の種類数を保存するので，条件を満たす数というのは，$10^6$ 以下の整数であって素因数の種類がちょうど $2$ 種であるようなものを $2$ 乗した値ということになります．素因数の種類数というのは実際に素因数分解すれば分かって，この問題の制約だと（ややこわいですが）それぞれ素因数分解して調べることができるので，クエリに答える前に解候補を列挙できます．
　解候補をソートしておけば，二分探索をすることでクエリに高速に答えを求められるので正答できます．

コード

constexpr int M = 1'000'000;

// 素因数分解 O( √N )
vector< long long > primeFactorization( long long N )
{
	if ( N == 1 )
	{
		return vector< long long >();
	}

	vector< long long > result;
	for ( long long p = 2; p * p <= N; p++ )
	{
		while ( !( N % p ) )
		{
			result.push_back( p );
			N /= p;
		}
	}
	if ( N != 1 )
	{
		result.push_back( N );
	}

	return result;
}

int main()
{
	VLL results;
	REP( i, 1, M + 1 )
	{
		const auto factors = primeFactorization( i );
		map< LL, int > counts;
		FOR( p, factors )
		{
			++counts[p];
		}

		if ( SZ( counts ) == 2 )
		{
			results.PB( LL( i ) * i );
		}
	}
	sort( ALL( results ) );

	IN( int, Q );
	REP( Q )
	{
		IN( LL, N );

		const auto it = prev( lower_bound( ALL( results ), N + 1 ) );
		cout << *it << '\n';
	}
	cout << flush;

	return 0;
}