POJ 1305 Fermat vs. Pythagoras

問題

x,y,zがN以下であるようなピタゴラス数（x^2+y^2=z^2を満たす自然数）のうち、
互いに素なものの個数および、N以下で、（互いに素ではないピタゴラス数も含む）どのピタゴラス数の1つにもなっていないような自然数の個数を出力せよ。

制約条件

N≦1000000

方針

ピタゴラス数は、二つの自然数のパラメータm,nを使い、
x=|m^2 - n^2|
y=2*m*n
z=m^2+n^2
と表すことができる。

これによりN以下のピタゴラス数を全列挙して、
問題文で求められているそれぞれの個数をカウントすればいい。

ソースコード

bool v[1000001];

int main()
{
	int N;
	while(~scanf("%d",&N)){
		rep(i,N+1)v[i]=0;
		
		int tuple=0, notuse=0;
		for(int m=2;m*m<=N;m++)for(int n=1;n<m&&n*n+m*m<=N;n++){
			
			int a=m*m-n*n, b=2*m*n, c=m*m+n*n, g=__gcd(a,b);
			g=__gcd(g,c);
			
			if(g!=1)continue;
			
			tuple++;
			for(int x=1;x*c<=N;x++)v[a*x]=v[b*x]=v[c*x]=1;
		}
		for(int i=1;i<=N;i++)if(!v[i])notuse++;
		
		printf("%d %d\n",tuple, notuse);
	}
	return 0;
}