PKU 2853. Sequence Sum Possibilities. [판정:TLE]

Milkskin 2009. 9. 8. 08:25

ㅋㅋ 이럴수가 :(

인수분해를 하고 나서 그 인수들을 다시 곱하는 방법으로 약수들을 다 구했습니다만 -_-;
(이때, 인수분해를 통해 나온 인수들에 2를 하나 추가해서 구했습니다)

여전히 TLE가 뜨네요 ㅠ (Run ID : 5826748)

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int integer( double d );
int isprime( int n );
void reset();
void factorize( int n );
int spread();
int possibility( int n );

// 1st row is primes, 2nd row is power of primes
int primeset[2][11] = {0};
int added[11] = {1, 0}; // 1 + power of prime
int *multiples;
int nod; // number of odd divisors

void main()
{
	int n;
	int *table;
	int i, temp;

scanf("%d", &n);
	table = (int *)malloc( sizeof(int) * (n+1) );

for( i = 1; i <= n; i++ )
	{
		scanf("%d %d", &temp, &table[i]);
	}

for( i = 1; i <= n; i++ )
	{
		printf("%d %d\n", i, possibility(table[i]));
	}

free(table);
}

int integer( double d )
{
	if( floor(d) == ceil(d) ) return 1;
	else return 0;
}

int isprime( int n )
{
	int i, sq;

if( n <= 1 ) return 0;
	if( n == 2 ) return 1;
	if( n % 2 == 0 ) return 0;

sq = (int)sqrt(n);
	for( i = 3; i <= sq; i += 2 )
	{
		if( n % i == 0 ) return 0;
	}

return 1;
}

void reset()
{
	int i;

for( i = 0; i <= 11; i++ )
	{
		primeset[0][i] = 0;
		primeset[1][i] = 0;
		added[i] = 0;
	}

free(multiples);
}

void factorize( int n )
{
	int i, j, k;

i = 3;
	k = 1;
	while( n > 1 && i <= n )
	{
		while( n % i == 0 )
		{
			primeset[0][k] = i;
			j = 0;
			while( n % i == 0 )
			{
				n /= i;
				j++;
			}
			primeset[1][k] = j;
			k++;
		}
		i += 2;
	}

i = 0;
	while( n % 2 == 0 )
	{
		n /= 2;
		i++;
	}
	primeset[0][k] = 2;
	primeset[1][k] = i + 1; // additional handling (+1)
}

int spread()
{
	int i, j, k;
	int cells = 1;

for( i = 0; i <= 11; i++ )
	{
		added[i] = 1 + primeset[1][i];
	}

for( i = 1; i <= 11; i++ )
	{
		if( primeset[0][i] == 2 ) nod = cells; // additional handling (nod)

cells *= added[i];
	}

multiples = ( int * )malloc( sizeof(int) * cells );

for( i = 0; i < cells; i++ )
	{
		multiples[i] = 1;

for( j = 1; primeset[0][j] != 0; j++ )
		{
			int div = 1;

for( k = 0; k < j; k++ )
			{
				div *= added[k];
			}

multiples[i] *= (int)pow( primeset[0][j], (i / div) % added[j] );
		}
	}

return cells;
}

int possibility( int n )
{
	double div, quo, rem;
	int temp, res;
	int i, det;

temp = n;
	rem = 0;
	while( temp > 0 && rem <= 1 )
	{
		rem += temp % 2;
		temp /= 2;
	}

// 2's exponents are can't be written as a "sum of a sequence of at least two consecutive positive integers"
	if( rem == 1 ) return 0;

if( isprime(n) ) return 1;

res = 0;
	factorize(n);
	temp = spread();

// odd divisors
	for( i = 1; i < nod; i++ )
	{
		div = multiples[i];
		quo = n / div;
		det = (int)(quo - floor(div / 2.0)); // det is determinant

if( integer(quo) && det >= 1 ) res++;
	}

// odd divisors * highest 2's exponents * 2
	for( i = temp - nod; i < temp; i++ )
	{
		div = multiples[i];
		quo = n / div;
		det = (int)(ceil(quo) - div / 2);

if( !integer(quo) && integer(quo*2) && det >= 1 ) res++;
	}

reset();

return res;
}