포함과 배제1 포함과 배제, 그리고 뫼비우스 함수 INTRO 적당히 꼼수를 써가면서 풀었는데 수학적으로 멋진 풀이를 가진 문제가 있어서 정리해본다. 제곱ㄴㄴ수 이 문제인데 풀 때는 몰랐지만 따로 공부한 후 다시 봤더니 포함과 배제, 더 나아가 뫼비우스 함수까지 개념을 접할 수 있는 아주 좋은 문제다. 이 문제를 풀어가는 과정에서 이 개념들을 접하면 더 이해하기도 쉬울 것 같다. 문제 해결 구간 내에서 square-free의 개수를 구하는 문제이다. square-free 수란 소인수 분해를 했을 때 제곱 인수가 없는 수를 뜻한다. f(n) = 1부터 n까지의 수 중에서 square free 한 수의 개수 위와 같이 f(n)을 정의하면 f(max) - f(min - 1) 을 출력하면 된다. 그럼 f(n)과 친해지기 위해 바로 식을 세우기 전에 손으로 직접 .. 2019. 10. 18. 이전 1 다음
