GCD SUM

GCD SUM

지난 토요일날 UVa 컨테스트 (World Finals 08 Warmup I) 가 열렸는데..
오오.. 평소와 다르게 엄청나게 많은 사람들이 참여하였다.. 왠일!!
이때문에 컨테스트 내내 홈피가 너무 느려서 서밋하고 결과 확인하는데 다들 고생이 많았다..;;

이번 컨테스트는 문제들이 참 아리까리하면서 괜찮았던것 같다..
그중에 관심을 끄는문제로 11424 - GCD Extreme 문제가 있는데.. GCD의 sum을 구하는 문제이다..

어떻게 풀어야하나 고민을하다가.. 일단 잘은 모르지만 euler phi를 구해야한다고 판단..
sieve를 응용해서 잽싸게 1부터 n까지 euler phi를 구했다.. 흠..
근데 그 이후부터 뭘해야하나.. 고민을하다가.. 결국 GG ㅠ_ㅠ;
나중에 사람들 토론을보니.. euler phi를 구하는거까지는 맞았네.. ㅋㅋ

근데.. 아직도 푸는방법을 모른다는거..;;;;

탑코더 포럼에서 누가 이문제와 관련된 논문을 올려놓았다..
나중에 천천히 읽어봐야지..

invalid-file

간단히 정리해보면 이런 내용이 있다..

sum{i = 1...n} (GCD(i, n)) = sum{d | n} (n * phi(d) / d))