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

ㅋㅋ 이럴수가 :(

인수분해를 하고 나서 그 인수들을 다시 곱하는 방법으로 약수들을 다 구했습니다만 -_-;
(이때, 인수분해를 통해 나온 인수들에 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; }