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

대망의 AC입니다 :D

최근에 나온 문제들 중 몇개는 도통 안풀리길래 잠시 접어두고

전에 풀다 막힌 것들 중 이놈을 다시 잡았습니다


알고리즘에 대한 이야기는 http://studyinglw.tistory.com/587 의 아랫부분에 나와있으니 참고하세요

#include <iostream> #include <cmath> using namespace std; bool isprime( int n ); int intpow( int m, int n ); void clear(); void factorize( int n ); void spread(); int possibility( int n ); int primeset[10] = {1, 0}; int primeexp[10] = {0}; int *factors; int elements = 1; // number of factors multiplied by odd factors int main() { int n; int *table; int i, temp; scanf("%d", &n); table = new 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])); } return 0; } bool isprime( int n ) { int i, sq; if( n <= 1 ) return false; if( n == 2 ) return true; if( n % 2 == 0 ) return false; sq = (int)sqrt((double)n); for( i = 3; i <= sq; i += 2 ) { if( n % i == 0 ) return false; } return true; } int intpow( int m, int n ) { if( m == 1 ) return 1; if( n == 0 ) return 1; int i; int res = 1; for( i = 1; i <= n; i++ ) { res *= m; } return res; } void clear() { int i; for( i = 0; i < 10; i++ ) { primeset[i] = primeexp[i] = 0; } primeset[0] = 1; } void factorize( int n ) { if( n % 2 == 0 ) { primeset[0] = 2; while( n % 2 == 0 ) { n /= 2; primeexp[0]++; } } int i = 1; int temp = 3; while( n > 1 ) { if( n % temp == 0 ) { primeset[i] = temp; while( n % temp == 0 ) { n /= temp; primeexp[i]++; } i++; } temp += 2; } } void spread() { int i, j, k; int noof; // number of odd factor int added[10] = {0}; // primeexp + 1 int exps[10] = {0}; // for spreading factors int temp; for( i = 1; i < 10; i++ ) { added[i] = primeexp[i] + 1; } elements = 1; for( i = 1; primeexp[i] != 0; i++ ) { elements *= added[i]; } factors = new int[elements]; noof = i - 1; for( i = 0; i < elements; i++ ) { temp = 1; for( j = 1; j <= noof; j++ ) { temp *= intpow( primeset[j], exps[j] ); } factors[i] = temp; k = noof; exps[k]++; while( exps[k] > primeexp[k] ) { exps[k-1]++; exps[k] = 0; k--; } } } int possibility( int n ) { int i; int temp, rem; int res = 0; 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; factorize(n); spread(); int max_divisor = (int)( ceil( (-1.0 + sqrt(1.0 + 8.0*n))/2.0 ) ); // odd divisors (except 1) for( i = 0; i < elements; i++ ) { if( factors[i] <= max_divisor ) { res++; factors[i] *= intpow( 2, primeexp[0]+1 ); } } res--; // except 1 // odd divisors * highest 2's exponents * 2 for( i = 0; i < elements; i++ ) { if( factors[i] <= max_divisor ) res++; } delete[] factors; clear(); return res; }

코딩할 때마다 느끼는거지만 -_-;

어느정도 난이도가 있는 문제는 왠만해선 100줄이 넘어가는군요 -_-;