PKU 2649. Factovisors. TLE

#include <iostream> #include <cmath> using namespace std; unsigned __int64 n; int GCD(int a, int b) { while (1) { if (a % b == 0 || b % a == 0) { break; } if (a > b) { a %= b; } else { b %= a; } } if (a % b == 0) { return b; } else { return a; } } bool isPrime(int a) { int i, limit; if (a <= 1 || a == 2) { return true; } else if(a % 2 == 0) { return false; } limit = sqrt((double)a); for (i = 3; i <= limit; i += 2) { if (a % i == 0) { return false; } } return true; } bool find(int m, int i) { if (m == 1) { return true; } if (i == 1) { return false; } else if (m <= i) { return true; } else if (isPrime(m) && m > i) { return false; } else { return find(m / GCD(m, i), i - 1); } } int main() { unsigned __int64 m; while(cin >> n >> m) { if (....) { cout << m << " does not divide " << n << "!" << endl; } else if (find(m, n) == true) { cout << m << " divides " << n << "!" << endl; } else { cout << m << " does not divide " << n << "!" << endl; } } }

보시면 아시겠지만 완전한 D&C(디바이드 앤 컨커) 기법이라 보기엔 애매한 코드입니다.

TL의 원인으로 탐색 범위를 충분히 좁히지 못해 일반 루프문보다 느리기 때문인것이 가장 큰 요소,

두번째로 isPrime을 지나치게 많이 체크한다는 점이 원인으로 보입니다.

Mr.K처럼 특정 케이스에 관한 부분은 ...으로 표기해 두었습니다.

완전한 D&C로 구현하는 솔루션이라면 아래와 같게 될 것입니다.

------------------- 인수들을 찾아 내어 확인 --------------------

m이 소수이면서 n이 큰 경우는 당연히 나눠지지 않는 경우입니다.

이 외에, m이 소수이면서 n보다 작은 경우라면 당연히 나눠집니다.

이 두가지 경우를 제외하고 본다면,

m에 대한 인수(굳이 소인수가 아니어도 됨)들을 찾아내어, 해당 인수들이 모두 n에 대해 만족하는지

확인해도 될 겁니다.

예를 들면...

find 함수가 인자로 source와 n을 받는다면 source(최초 실행시는 m이 인자로 들어옵니다.)가 k로 나누어

떨어질 때 아래와 같은 방식으로 탐색범위를 줄일 수 있습니다.

bool find(int source, int n) { ...... return find(k, n) && find(source / k, n); }


예상 코드이기 때문에 실질적인 코드와는 형태가 상당히 다를 것입니다. 인자 갯수부터 달라지겠지요.

제가 올린 코드를 단순하게 루프형으로 분석해본다면 아래와 같습니다.

-------------------------- 단순 인수분해 처리법 ------------------------

1. m이 1이라면 당연히 나누어 떨어짐.


2. n에 대한 이터레이터(for문을 이용할 경우 i)가 n회 이상 증가, 혹은 감소시 루프횟수를 넘었기

때문에 나누어 떨어지지 않음.


3. m이 소수이고, n보다 크다면 나눠지지 않음,


4. m이 소수이나, n보다 작다면 나눠짐.


5. m이 소수가 아니라도, n보다 작다면 나눠짐.


6. m이 소수가 아닐때, n보다 크다면 n과의 GCD를 구함.


7. m을 GCD로 나누고, 그 몫에 대해 n 에서 1을 감소시킨 값에 대해 1.부터 다시 수행.

이 경우 아시겠지만, 루프 중 시간을 상당히 잡아먹는 isPrime을 자주 호출하게 됩니다.

이에 따라 변경한 알고리즘은 다음과 같습니다.

----------------------- 단순 인수분해 솔루션, isPrime 적게쓰는 변경형 ---------------------


1. m이 1이면 당연히 나눠 떨어짐.


2. n에 대한 이터레이터(for문을 이용할 경우 i)가 n회 이상 증가, 혹은 감소시 루프횟수를 넘었기

때문에 나누어 떨어지지 않음.


3. m과 n의 GCD를 구함.


4. GCD가 1이고 m이 n보다 크며 소수이면 나누어 떨어지지 않음.


5. GCD가 1이고 m이 n보다 크며 소수가 아니면 n을 1 감소시킨 후 1.부터 재수행.


6. GCD가 1이고 m이 n보다 작으면 소수에 상관없이 나누어 떨어짐.


7. GCD가 1이 아니라면 m을 GCD로 나눈 값과 n을 1 감소시킨 값에 대해 1. 부터 재수행.

if문의 중첩 형식을 변경함으로써 isPrime의 호출 방식을 상당히 줄일 수 있습니다.

현재 몸상태가 말이 아닌지라 코드로 옮기지 못했습니다만,

기존 알고리즘은 확실히 TL이고, 이 isPrime을 적게 쓰는 변형은 코드를 아직 안써봤으므로 확신이 없습니다.

다만, 여전히 isPrime의 호출횟수가 과도합니다.