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

ㅋㅋ 또 TLE입니다 -_-;

첫번째 TLE는 요놈이구요 (Run ID : 5768623)
#include <stdio.h> #include <stdlib.h> #include <math.h> 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; } int possibility( int n ) { double div, quo, rem; int temp, res; 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; div = 2; res = 0; while( div < n ) { quo = n / div; temp = (int)(ceil(quo) - div / 2); // temp is determinant if( !integer(quo) && integer(quo*2) ) { if( temp < 1 ) break; else res++; } div += 2; } div = 3; while( div < n ) { quo = n / div; temp = (int)(quo - floor(div / 2.0)); // temp is determinant if( integer(quo) ) { if( temp < 1 ) break; else res++; } div += 2; } return res; } 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); }


두번째 TLE는 요놈입니다 -_-; (Run ID : 5781754)
#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}; // except 2 int added[11] = {1, 0}; // 1 + power of prime int *multiples; 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; while( n % 2 == 0 ) { n /= 2; } i = 3; k = 1; while( n > 1 ) { while( n % i == 0 ) { primeset[0][k] = i; j = 0; while( n % i == 0 ) { n /= i; j++; } primeset[1][k] = j; k++; } i += 2; } } 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++ ) { 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; div = 2; res = 0; while( div < n ) { quo = n / div; det = (int)(ceil(quo) - div / 2); // det is determinant if( !integer(quo) && integer(quo*2) ) { if( det < 1 ) break; else res++; } div += 2; } factorize(n); temp = spread(); for( i = 1; i < temp; i++ ) { div = multiples[i]; quo = n / div; det = (int)(quo - floor(div / 2.0)); if( integer(quo) && det >= 1 ) res++; } reset(); return res; }



계산해야 하는 수를 M이라고 했을 때

M을 짝수로 나누었을 때는
그 몫이 0.5 단위로 떨어지면 연속된 자연수의 합으로 나타날 가능성이 있는 것이고

M을 홀수로 나누었을 때는
그 몫이 정수로 떨어지면 연속된 자연수의 합으로 나타날 가능성이 있는 것입니다 -_-;

문제에서 예시로 나온 1800의 경우,
인수분해를 하면 2^3 × 3^2 × 5^2 로 분해가 되는데

이 때문에 16으로 나누면 자연스럽게 몫이 0.5 단위로 떨어지게 되고, (112.5)

이 말인 즉슨 112.5 + 112.5 + … + 112.5 (16개) = 1800 과 같은 결과를 줍니다
문제에서 요구하는 것은 연속된 자연수의 합으로 나타낼 수 있는가를 물어보는 것인데

위의 합을 앞부분 8개, 뒷부분 8개로 나누어서
앞부분에서 하나 뒷부분에서 하나를 대응시킨 후, 앞부분에서 0.5단위를 떼서 뒷부분에 붙이면 됩니다


뭔소린고 하니

112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 = 1800
이것을

(112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5) + (112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5 + 112.5) = 1800
이렇게 나누고

(105 + 106 + 107 + 108 + 109 + 110 + 111 + 112) + (113 + 114 + 115 + 116 + 117 + 118 + 119 + 120) = 1800
가운데에서 가까운 놈들끼리 대응시킨 후
각각 0.5, 1.5, 2.5, … 를 떼서 뒷부분에 붙이면 이렇게 됩니다
이러면 문제에서 요구하는 조건에 맞게 되지요 -_-;


홀수로 나눌 때도 1800을 예로 들어보면
일단 3의 배수이니까 3으로 나누어 떨어집니다, 몫은 600이구요

그러면 600 + 600 + 600 = 1800 이 되고, 이것은 곧 599 + 600 + 601 = 1800 을 만들 수 있게 합니다

마찬가지로,
일의 자리가 0이므로 5로 나누어 떨어지겠네요, 몫은 360입니다
이것은 358 + 359 + 360 + 361 + 362 = 1800 을 만들 수 있게 합니다



이런 식으로 찾으면 됩니다만,
위에서 연속된 자연수의 합으로 나타날 가능성이 있다 라고 했습니다 -_-;

위처럼 나누어 떨어져도 문제에서 요구하는 조건에 안맞을 수도 있다는 말이죠 -_-;
그건 직접 찾으시길 ㅋㅋ