https://www.acmicpc.net/problem/1557
1557번: 제곱 ㄴㄴ
어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K
www.acmicpc.net
생각하는데 오래걸린 문제
처음에 위의 사진처럼 엄청 무식하게 접근했다가
조언을 받아서 뫼비우스 함수라는 걸 이용해서 문제를 해결했다.
인터넷에서 찾은 분이신데,
뫼비우스 함수를 코드와 함께 깔끔하게 정리해주셨다.
포함과 배제, 그리고 뫼비우스 함수
INTRO 적당히 꼼수를 써가면서 풀었는데 수학적으로 멋진 풀이를 가진 문제가 있어서 정리해본다. https://www.acmicpc.net/problem/1016 이 문제인데 풀 때는 몰랐지만 따로 공부한 후 다시 봤더니 포함과
ohgym.tistory.com
***** 검열됨 *****
현재 제 블로그 글의 조회수 1위를 차지하고 있는 글이 지금 이 글입니다.
아무래도 solved.ac 기준 티어가 높아 소위 말하는 '날먹' 현상이 일어나고 있다는 의심을 지울수가 없었고,
이에 자율적인 판단에 따라 해당 글의 소스코드를 블라인드 처리하도록 하겠습니다.
대부분은 소스복붙을 하지 않으실 분들이라 생각하지만 혹시몰라 조치하였습니다
앞으로도 solved.ac 기준 다이아몬드 티어를 넘기는 문제들에 대하여 소스코드 공개를 닫을 생각이에요
바로 소스설명
setup 함수가 뫼비우스함수에 i를 넣었을때의 반환값을 arr[i]에 저장해주는 함수.
범위는 넉넉하게 100만으로 잡아주었다.
f함수가 k이하의 square free number의 갯수를 구해주는 함수.
이또한 뫼비우스함수를 잘 사용하면 쉽게 구할 수 잇다.
사실 여기까지 풀면 왠만해서는 풀리는거같다.
메인함수에서는 설정해줫고 k 받은 다음
입력받은 k의 값이 커질때 f(k)가 증가하는것이 자명하므로
이분탐색이 가능하다는 점을 이용해서 이분탐색 해준 뒤 값을 출력해주면 된다.
이거푸는데 일주일정도 걸렷으니
이건 더러운 AC.
+ 노가다하고 살짝 손봣을때 26이라는값이 계속 나와서 당황했었는데,
f() 함수 내의 arr[i]*k/(i*i)에서 i*i를 괄호로 안묶어주면 이런문제가 생기는거같다.
어떻게 맨날 ps하는데 이런걸 모르지 진짜로
능지 ㅠㅠ
사실 노가다 ver2 소스에서도(소스를 네번정도 갈아엎었다) 26이 나왔던거같은데
정말로다가 그냥 익숙해지는수밖에 없을거같다 ㅠㅠ
