GCD SUM

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

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

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

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

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


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

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


'Problem Solving > Algorithm notes' 카테고리의 다른 글

Combination 개수 구하기 (Pascal's Triangle)  (2) 2009.02.07
Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12

Leave a Comment


to Top