[백준] 14862 최대공약수 기댓값

이문제는 결론적으로 최대공약수의 합을 수식을 승법적 함수를 쓰는것까지 나타내서 시간을 최적화 해야 통과되는 문제다. 즉, 테스트 케이스 하나를 Harmonic Lemma를 사용한다면 에 계산 가능하다. N은 모듈러 역원으로 구해주면 된다. 위방법으로 제출했을때는 시간초과가 나게된다. 좀더 최적화를 해보자. 함수 g를 Linear sieve로 O(N)에 전처리해둔다면 Harmonic Lemma 없이도 한 테스트 케이스가 O(N)에 처리되기 때문에 맞을 수 있다. 하지만 여기서 Harmonic Lemma 까지 써준다면 정도로 빠르게 통과 가능하다. 실제로 28ms 나왔다....

[백준] 14862 최대공약수 기댓값에 대한 요약내용입니다.

자세한 내용은 아래에 원문링크를 확인해주시기 바랍니다.

원문링크 : [백준] 14862 최대공약수 기댓값