pce913   1달 전

안녕하세요. 백준온라인저지의 고수님들.

시간초과를 해결하기 위한 질문을 올립니다.

저의 전략은

1. N의 '소수인 약수' 들을 구한다.

2. A와 B 범위 사이에서  1 에서 구한 소수인 약수들과 서로소가 아닌 녀석들를 빼준다.

3.  2에서 중복된 값을 빼줬을 수 있으므로 '포함배제'원리를 사용해서 최종 답을 구한다.

이것인데요.

결론은 시간초과가 나더라구요.

N의 범위가 10억 이하이므로 이때 나올 수 있는 소수인 약수의 갯수는 많으면 9개까지 나올 수가 있는데요.

그렇게 되면 3의 포함배제의 원리에서 9의 9제곱번 반복이 일어나므로 시간 초과가 날것 같더라고요. 

또, 1에서도 시간이 꽤나 오래걸리구요.

조금더 효율적인 전략이 없을까요?

한번만 도와주십쇼 형님들!


zlzmsrhak   1달 전

1. (1~B에서 N과 서로소인 수의 갯수) - (1~(A-1)에서 N과 서로소인 수의 갯수) 로 구하는 것이 구현상에서 조금 더 편합니다.

2. 포함과 배제는 각 원소가 "포함 되거나 안되거나" 로 가짓수를 구하기 때문에 2^9의 연산이 필요합니다.

예를 들어 48까지의 자연수 중 30 = 2*3*5와 서로소인 수들의 갯수는,

48/1 - 48/2 - 48/3 - 48/5 + 48/(2*3) + 48/(2*5) + 48/(3*5) - 48/(2*3*5) = 13으로 계산됩니다.

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