PKU 2649. Factovisors. [판정:AC]

소스가 좀 길긴 한데

구현 자체는 그리 어렵지 않다고 생각합니다


#include <stdio.h> #include <math.h> int isPrime( int ); void factorize( int ); void factovisor( int, int ); // 1st row is primes, 2nd row is power of primes int primeSet[2][10] = {0}; int judge[10] = {0}; void main() { int n; int m; while( scanf("%d %d", &n, &m) != EOF ) { if( m == 0 ) printf("%d does not divide %d!\n", m, n); else factovisor( m, n ); } } int isPrime( int x ) { if( x <= 1 ) return 0; else if( x == 2 ) return 1; else if( ( x!=2 )&&( x%2 == 0 ) ) return 0; // for all x > 2 with x is even else { int i; for( i = 3; i <= sqrt(x); i += 2 ) { if( x%i == 0 ) return 0; } return 1; } } void factorize( int x ) { int i; int j; int k; k = 0; if( x % 2 == 0 ) { for( i = 0; x % 2 == 0; i++ ) { x /= 2; } primeSet[0][0] = 2; primeSet[1][0] = i; k++; } i = 3; while( x > 1 ) { while( x % i == 0 ) { primeSet[0][k] = i; for( j = 0; x % i == 0; j++ ) { x /= i; } primeSet[1][k] = j; k++; } i += 2; } } void factovisor( int x, int y ) { int i; int j; int k; int amount; // power of primes in y (exponent) int ppower; // power of primes in y (calculated) if( isPrime(x) ) { if( x <= y ) printf("%d divides %d!\n", x, y); else printf("%d does not divide %d!\n", x, y); } else { factorize(x); // compare to factorized x for( j = 0; primeSet[0][j] > 0; j++ ) { if( primeSet[0][j] * primeSet[1][j] <= y ) { judge[j] = 1; } else { amount = 0; for( i = primeSet[0][j]; i <= y; i += primeSet[0][j] ) { ppower = 1; for( k = 1; ; k++ ) { ppower *= primeSet[0][j]; if( ( i % ppower == 0 )&&( i % ( ppower*primeSet[0][j] ) != 0 ) ) break; if( k > primeSet[1][j] ) { k = 1; break; } } amount += k; } if( amount < primeSet[1][j] ) judge[j] = 0; else judge[j] = 1; } } for( i = 0; i < j; i++ ) { if( judge[i] == 0 ) break; } if( i < j ) printf("%d does not divide %d!\n", x, y); else printf("%d divides %d!\n", x, y); // set re-initialize for( i = 0; i < 2; i++ ) { for( j = 0; j < 10; j++ ) { primeSet[i][j] = 0; } } for( i = 0; i < 10; i++ ) { judge[i] = 0; } } }


isPrime함수는 input이 소수인지 아닌지를 판별하는 함수입니다
dizies님의 포스트에도 나와있지만 아마 그것보다 조금 더 빠르지 않을까 생각해봅니다

factorize함수는 input을 소인수분해하여 primeSet의 적당한 부분에 저장합니다

factovisor함수는 주어진 m과 n에 대해 문제에서 요구하고 있는 것을 만족하는지 판단하는 함수입니다



대략적인 설명을 하면

처음 두 수를 입력받았을 때, 그것이 특정 케이스*라면 '불가'를 출력하고
특정 케이스가 아니라면 factovisor함수를 호출합니다

factovisor함수는 우선, m이 소수인지 판별해서 소수라면 if문을 통해 '가' 혹은 '불가'를 출력하고

m이 소수가 아니라면, m에 대해서 factorize함수를 호출합니다
즉, m을 소인수분해합니다

그리고나서 그것과 n!의 인수들을 비교하여 judge의 적당한 부분에 저장하고,

judge를 가지고 판단하여 '가' 혹은 '불가'를 출력합니다

그리고 다음 입력을 대비해 primeSet과 judge를 0으로 초기화하지요



일부러 일부 내용을 지우고 올렸습니다 (오늘 올라온 문젠데 오늘 답이 올라오면 김샐 것 같아서)

풀 소스를 원하는 분은 댓글 달아주세요//
댓글 보는대로 수정해드립니다

뭐, 풀 소스를 원하는 댓글이 없어도 며칠 지나면 수정할거긴 합니다만 -_-;


*특정 케이스: 역자 주 3번째에 언급한 그 케이스입니다

---------------------------------------

(글 수정 시작 : 4일 pm 11시 45분 경)

factovisor함수의 조건문이 false를 받았을 때, 즉 x가 소수가 아닐 때

소인수분해 함수가 호출된 후의 내용에 대해 설명하겠습니다

그 전에, 몇가지 예를 보도록 하겠습니다

1. 32(= 2^5)는 10!을 나눕니다

2. 27(= 3^3)도 10!을 나눕니다

3. 16(= 4^2)도 10!을 나눕니다

4. 25(= 5^2)도 10!을 나눕니다

이게 무슨 뜻인지 아시겠습니까?

10! = 1×2×3×4×5×6×7×8×9×10 이므로

2의 거듭제곱으로 '나누기'를 시도할 경우 적어도 다섯번까지는 당연히 나눌 수 있습니다
( 10! = 1×2×3×4×5×6×7×8×9×10 )

3의 거듭제곱으로 '나누기'를 시도할 경우 적어도 세번까지는 당연히 나눌 수 있습니다
( 10! = 1×2×3×4×5×6×7×8×9×10 )

4의 거듭제곱으로 '나누기'를 시도할 경우 적어도 두번까지는 당연히 나눌 수 있습니다
( 10! = 1×2×3×4×5×6×7×8×9×10 )

5의 거듭제곱으로 '나누기'를 시도할 경우 적어도 두번까지는 당연히 나눌 수 있습니다
( 10! = 1×2×3×4×5×6×7×8×9×10 )

즉, k로 n!을 나눌 때, 'n을 k로 나눈 몫'에 해당하는 횟수만큼은 당연히 나눌 수 있습니다

1부터 n까지의 수들 중에 k의 배수에 해당하는 부분만 체크하면 되기 때문이죠

그런데, 이 방법으로 계산을 하게 되면 '6은 오로지 한번 10!을 나눌 수 있다'가 되는데 (10 ÷ 6 = 1 … 4 이므로)

사실 2×3과 4×9가 있기 때문에 6은 최대 네번까지 나눌 수 있습니다

그러므로 이 방법을 '소수'에 대해서만 적용하면 깔끔하게 비교할 수 있습니다

이제 그럼 나머지 소스에 대해 분석해봅시다

가장 바깥에 위치한 for문은 primeSet[0][j]에 저장된 것이 소수일 때까지만 돌아갑니다

그 안에 위치한 if문은 'm의 소인수와 그 소인수의 개수를 곱한 것이 n보다 작거나 같은가'를 판별하는 부분입니다

위의 예시를 참고하면, 10을 2로 나눈 몫이 5이므로

m을 소인수분해 했을 때 2가 다섯개 이하 존재한다면 10!의 소인수를 일일이 체크하지 않아도 당연히 나눌 수 있게 됩니다
m을 소인수분해 했을 때 2가 여섯개 이상 존재한다면 위의 방법을 사용했을 때는 '나눌 수 있음'이 보장되지 않습니다

이 if문의 결과가 true이면 해당하는 소수 primeSet[0][j]에 대응되는 judge[j]에 1을 대입하고

false이면 본격적으로 m의 소인수의 개수를 n!에서 체크하도록 합니다

'n! 안에 존재하는 m의 소인수의 개수'를 amount에 저장합니다

i에 소인수를 대입하고 그의 배수에 대해 하나씩 체크하면서 amount를 증가시킵니다

이 때, n!을 구성하는 자연수들(&소인수의 배수) 중

'소인수의 거듭제곱'꼴로 표현된 수가 존재한다면 그 수에 대해서는 소인수의 개수가 거듭제곱의 지수와 같게 됩니다

그리고 거듭제곱꼴로 표현되지 않는 수에 대해서는 소인수의 개수가 1개만 존재한다고 하였습니다

(현재 소스에서는 수정되어있습니다)

위의 예시를 참고하면, 10보다 작거나 같은 3의 배수는 3, 6, 9가 있는데

이들 중 3과 9는 3의 거듭제곱으로 표현이 되고(3^1, 3^2), 여기에 존재하는 3의 개수는 거듭제곱의 지수(1, 2)와 같습니다
그리고 3의 거듭제곱으로 표현되지 않는 6은 3이 1개만 존재하겠지요
(써놓고 보니 이 부분에서 예외 케이스가 발생하는군요, 근데 이거 처리 안해도 AC 뜹니다 -_-; 아마 pku 테스트케이스에 없는듯)

어쨌든 그렇게 해서 judge에 1 또는 0이 대입되고서 for문을 탈출하면, j는 그대로 두고

judge에 대해 i를 0부터 돌려서 소수의 개수와 judge[i]에 1이 대입된 회수를 비교합니다

그래서 i < j이면 m이 n!을 나눌 수 없다고 출력하고,

아니라면 i와 j가 같을 테니 m이 n!을 나눌 수 있다고 출력하는겁니다

(글 수정 완료 : 5일 am 1시 5분 경)

----------------------------------

(최종(?) 수정 : 5일 am 1시 30분 경)

새로 발견된 예외 케이스 처리했습니다 (& 기존 소스에 적용시켜놓았습니다)

(변수 하나를 더 선언했는데 오히려 메모리 사용량이 줄었다?!)