TopCoder SRM 567, Division 1, Level 1 : TheSquareRootDilemma

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12377

概要

SSR 関数を以下のように定義する
　
二つの整数 N, M について、 かつ で SSR( A, B ) が整数となるような A, B の組の個数を求めよ。

解法

まず、SSR 関数の式を展開します。すると、
　
です。
従って、 が整数となる、すなわち、AB が平方数となる組を見つければ良いことになります。

ここで、AB の内の片方、A を固定することを考えます。
すると、A に二つ含まれる素因数を根号の外に出すことができ、残った素因数の積 a について、掛けて平方数になるような整数を見つければ良いことになります。
平方数に平方数を乗じた値は平方数であるので、a * a * 平方数 は平方数となります。
これを a * ( a * 平方数 ) と書き表わせば、B の値は a * 平方数 であることが分かります。
従って、A の固定と a * 平方数 を総当りすることで解くことができます。

コード

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

class TheSquareRootDilemma
{
public:
	int countPairs( int N, int M )
	{
		int res = 0;

		REP( i, 1, N + 1 )
		{
			res += solve( i, M );
		}

		return res;
	}

	int solve( int a, int M )
	{
		for ( int i = 2; i * i <= a; i++ )
		{
			while ( !( a % ( i * i ) ) )
			{
				a /= i * i;
			}
		}

		int res = 0;

		for ( int i = 1; i * i * a <= M; i++ )
		{
			res++;
		}

		return res;
	}
};