torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 582, Division 2, Level 1 :

概要

a < b かつ a * b * b = N となる正整数 a, b が存在するかどうか判定せよ。

解法

N 未満の a, b のうち a < b を満たすものを総当りして、等式が成り立つものがあれば Yes です。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

class SemiPerfectSquare
{
public:
	string check( int N )
	{
		REP( a, 1, N )
		{
			REP( b, a + 1, N )
			{
				if ( a * b * b == N )
				{
					return "Yes";
				}
			}
		}

		return "No";
	}
};