rootsquare   2년 전

이 문제를 풀다가 막히시면, 아래에 제시해주는 몇 가지 힌트를 참고해 보세요.

1. 입력받은 수의 인수를 구해서 어떻게 해야 하는가?

먼저 에라토스테네스의 체로 소수들을 10^6 범위 내에서 찾아주시고, 입력받은 수의 소인수를 찾으세요. 이후 찾으신 소인수들을 적절히 곱해서 인수를 만들어 주시고, 이것으로 입력받은 수를 나눠 해당 인수의 배수의 개수를 구합니다. 소인수를 적절히 곱하는 과정은 브루트포스를 활용하세요.

이후 포함과 배제의 원리에 따라 입력받은 수와 서로소가 아닌 수의 합집합을 구해 주시면 됩니다.

2. 입력으로 받는 수의 소인수는 최대 몇 가지(서로 다른)인가?

2부터 순차적으로 소수들을 곱하면 다음과 같습니다.

2*3*5*7*11*13*17*19*23*29*31=200,560,490,130 이고, 여기에 다음 소수인 37을 곱하면 10^12보다 커집니다.

고로 입력으로 가능한 모든 수들의 소인수의 종류는 최대 11개입니다. 2^11=2048이므로, 비트마스킹 등을 활용한 브루트포스로 1번의 과정을 수행할 수 있습니다.


3. 입력받은 수가 1000000(10^6)보다 큰 소수를 인수로 갖는다면 어떻게 해야하는가?

1번의 과정을 통해 입력받은 수를 소인수분해하면, 999983(10^6까지의 소수 중 가장 큰 수입니다.)까지 나누고 맨 나중에 나눠지지 않고 남은 수가 있을 수도 있습니다. 이를 T라고 합시다.

T는 10^6보다 작은 소수로 나눠 떨어지지 않으며, (10^6)<T<(10^12)입니다.10^6보다 큰 소수 중 가장 작은 수가 1000003인데, 이를 제곱하면 10^12보다 커집니다.

따라서 T는 항상 소수입니다.

아래에 제가 몇 가지 테스트케이스를 첨부해 두었습니다. 확인해보시기 바랍니다.

creeperss85   1년 전

3번 힌트덕분에 시간초과를 해결할 수 있었습니다. 소수 판별할때 꼭 sqrt(n) 이하로 하거나 손풀이로 최대값을 지정해 주는 일이 필요함을 깨달았네요. 감사합니다. 

w8385   1년 전

3번 힌트에서 10^6 이상의 소수 처리에 대한 힌트를 얻었습니다.

감사합니다 :)

hacastle   10달 전

루트스퀘어! 루트스퀘어! 루트스퀘어!

댓글을 작성하려면 로그인해야 합니다.