풀이
Mobius function와 Mertens function로 풀이했다.
편의상 "제곱ㄴㄴ수"는 SFI(Square Free Integer, 제곱 인수가 없는 정수)라고 부르겠다.
Mobius function
Mobius function은 다음의 조건에 따라 값을 반환하는 함수다.
- 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 1
- 제곱 인수가 없을 때, 소인수의 개수가 홀수이면 -1
- 제곱 인수가 있는 정수이면 0
Mertens function
Mertens function는 Mobius function의 부분합으로, 입력받은 수 까지 존재하는 SFI의 개수를 알 수 있다.
K의 최댓값 즉, 1,000,000,000번째 SFI를 구하기 위해서는 Mobius function의 반환값들을 얼마나 저장해야 하는가?
이는 주어진 K에 대해 SFI의 밀도를 구할 수 있는 Quadratfrei Function을 통해 알 수 있었다.
개발자가 아니라 수학자인가?
약 61%의 정수가 SFI이기 때문에, 약 1,639,344,262가 1,000,000,000번째 SFI라고 추측할 수 있다.
1,639,344,262보다 큰 제곱근은 40,489이므로, Mobius function의 반환값들은 넉넉하게 42,000개 저장해주면 된다.
충분한 Mobius function의 반환값들을 구했으니, Mertens function를 이용해 SFI의 개수를 구할 수 있다.
마지막으로, SFI의 개수와 입력받은 K가 동일할 때까지, 0 ~ 2K에 대해 Binary Search을 하면된다.
+ 수정
이항계수 성질과 SFI 밀도는 관련이 없습니다.
소스코드
점수를 올리기 위한 카피코드가 너무 많이 발견되어 코드를 플레 3 이상의 코드는 블로그에 올리지 않기로 결정했습니다.
출처
1557번: 제곱 ㄴㄴ
어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K
www.acmicpc.net
뫼비우스 함수 - 위키백과, 우리 모두의 백과사전
수론과 조합론에서, 뫼비우스 함수(Möbius函數, 영어: Möbius function)는 정수가 제곱 인수가 없는 정수인지 여부에 따라 분류하는 곱셈적 함수이다. 뫼비우스 반전 공식에 사용되며, 리만 가설과도
ko.wikipedia.org
포함과 배제, 그리고 뫼비우스 함수
INTRO 적당히 꼼수를 써가면서 풀었는데 수학적으로 멋진 풀이를 가진 문제가 있어서 정리해본다. https://www.acmicpc.net/problem/1016 이 문제인데 풀 때는 몰랐지만 따로 공부한 후 다시 봤더니 포함과
ohgym.tistory.com
Characteristic function of squarefree numbers - OeisWiki
The quadratfrei function is the characteristic function of squarefree numbers. The quadratfrei function q ( n ) {\displaystyle \scriptstyle q(n)\,} is given by q ( n ) ≡ χ { s q u a r e f r e e } ( n ) = | μ ( n ) | , {\displaystyle q(n)\,\equiv \,\chi
oeis.org
'PS > Baekjoon Online Judge' 카테고리의 다른 글
| [백준 10994] 별 찍기 - 19 [C] (0) | 2021.08.07 |
|---|---|
| [백준 10995] 별 찍기 - 20 [C] (0) | 2021.08.06 |
| [백준 1764] 듣보잡 [C/C++] (0) | 2021.08.06 |
| [백준 1260] DFS와 BFS [C] (0) | 2021.08.05 |
| [백준 2630] 색종이 만들기 [C] (0) | 2021.08.05 |