http://todayhumor.com/?programmer_4869 << 원글
이 문제는 절대로 gcd를 빨리 계산하는 문제가 아닙니다.
2차원 세그먼트 트리 문제입니다.
재밌는 이야기 1.
저 당시 ioi는 개혁의 시대였습니다.
기존의 단순 알고리즘 문제에서 벗어나 좀 창의적인 문제들을 내려고 했지요
그리고 저 대회의 첫날 (이틀간 총 6문제를 풉니다) 2번 문제가 artclass...
그림 파일을 받아서 그게 무슨 형식의 그림( 추상화 / 실물화 등등 )인지 알아맞추는 문제였는데,
당연하지만 명확한 해답이 없어서 엄청난 항의를 받았습니다. (색맹에게 불리하다는 의견도 있었음)
그리고 두번째 날 원래 나와야하는 3번문제 대신 저 Game 문제가 출제되게 됩니다.
과연 그 때 저 사람들은 무슨 문제를 준비하고 있었던 걸까요...
급하게 준비한 문제라 그런지 대회 공식 솔루션이 없습니다.
2.
ioi 문제는 풀 때, 알고리즘을 계산해 볼 때 루프를 도는 횟수가 초당 2억번이 넘으면 일단 잘못 푸셨다고 봐도 됩니다.
3.
이 블로그에 해답이 아주 잘 설명되어 있습니다.
글쓰기