[UVa]11342:Three-square

這題請建表。
建表有兩個方式：
一個是像質數篩法那樣，
將a*a+b*b+c*c的那格填入答案。
另外一個是比較慢，也是下面的程式碼的作法，
直觀地真的去找每個數的答案，
但是要注意a,b,c的範圍避免TLE。

[C](0.568)

	#include<stdio.h>
	#include<math.h>
	#define ERROR 0.0000001
	int main()
	{
	int answer[50005][3] = {0};
	int n;
	for( n = 1 ; n <= 50000 ; n++ )
	{
	unsigned int a, b, c;
	int ok = 0;
	for( a = 0 ; a*a <= n/3 ; a++ )
	{
	for( b = a ; b*b <= (n - b*b - a*a) ; b++ )
	{
	double temp = sqrt((double)(n-b*b-a*a));
	c = temp + ERROR;
	if( (double)c == temp )
	{
	ok = 1;
	break;
	}
	if( ok )
	break;
	}
	if( ok )
	break;
	}
	if( ok )
	{
	answer[n][0] = a;
	answer[n][1] = b;
	answer[n][2] = c;
	}
	else
	answer[n][0] = -1;
	}
	int N;
	while( scanf( "%d", &N ) != EOF )
	{
	int i;
	unsigned int K;
	for( i = 0 ; i < N ; i++ )
	{
	scanf( "%u", &K );
	if( answer[K][0] == -1 )
	printf( "-1\n" );
	else
	printf( "%d %d %d\n", answer[K][0], answer[K][1], answer[K][2] );
	}
	}
	return 0;
	}

view raw UVa11342.c hosted with ❤ by GitHub