Codeforces #183, Division 2, A : Pythagorean Theorem II

問題文

http://codeforces.com/contest/304/problem/B

概要

整数 n が与えられる。
各辺の長さが整数であり、c を斜辺とする直角三角形のうち、次の条件を満たすものの数を求めよ。

• 

解法

a, b の長さを決めたとき、c の二乗の値が決まります。
平方数の表を予め作っておいて、全ての a, b の組について c の二乗の値が表に存在するかを二分探索で求めます。
存在するならば直角三角形が作れるのでカウントを増やします。

コード

typedef vector<int> VI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()
#define PB( n ) push_back( n )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI squares;
	REP( i, 1, n + 1 )
	{
		squares.PB( i * i );
	}

	int res = 0;
	REP( a, 1, n + 1 )
	{
		REP( b, a, n + 1 )
		{
			res += binary_search( ALL( squares ), a * a + b * b );
		}
	}

	cout << res << endl;

	return 0;
}