구사과

(Summerteeth, 1999)

http://news.naver.com/main/read.nhn?mode=LSD&mid=sec&oid=025&aid=0002534087&sid1=001 서울대는 몇 년 전 지원자들의 생활기록부에 올림피아드 관련 수상 실적이 지워지지 않았다고 해서 교육부로부터 경고를 받았다고 한다. 교육부의 재정 지원을 받는 서울대로서는 이런 통제에서 벗어나기 힘들 것이다. 고교 3년을 온통 컴퓨터 프로그래밍에 미쳐 생활한 학생의 생활기록부에 이걸 제외하고 무엇을 적으란 말인가. 입시전형을 다양화해 다양한 자질을 가진 학생들을 선발하도록 하겠다더니 이런 인재들의 진입은 원천적으로 봉쇄하고 있다. 대통령이 “창의성을 갖춘 인재가 국가 경쟁력을 좌우하는 시대를 살아가고 있다” “학생의 꿈과 끼를 키우는 교육을 해야 한다”고 ..

http://www.spoj.com/problems/IE3쿼리당 Sqrt(N)lgN에 풀 수 있다. N 이하의 Square 수가 모두 Sqrt(N)개 있을 텐데, 이걸 단순히 포함배제로 하면 - * 2^2의 배수 더해주고 - * 3^2의 배수 더해주고 - * 6^2의 배수 빼주고 - * 4^2의 배수는 냅두고 - * 5^2의 배수 더해주고 - ( ..... ) 말도 안되는 시간 복잡도가 나오겠지만 이 때를 위해서 뫼비우스 함수라는 것이 존재한다. 뫼비우스 함수 f(n)은 : * f(n)이 제곱수로 나눠지면 0 * f(n)의 소인수 수가 홀수면 -1 * 아니면 1 으로 정의되는데 이걸 쓰면 저걸 어떻게 해주면 되나면 * f(6) * 6^2의 배수 더하고 * f(5) * 5^2의 배수 더하고 (....) 이..