https://www.acmicpc.net/problem/3844
문제요약
- D를 찾아야함
- 완전제곱수
- N 이하의 서로다른 자연수의 곱
- N 은 1천만 이하
접근법
- 완전제곱수 + 서로다른 자연수의 곱을 어떻게 엮을까
- N이하의 자연수는 소수의 곱으로 표현 가능
- N이하의 자연수에서 소수 p가 몇 번 등장하는지 세어봄
- 잘 계산해내었다고 치고,
- 짝수번 등장 => 완전제곱수에 쓰일 수 있겠음
- 홀수번 등장 => 애매한데
- 홀수번을 짝수번으로 바꿀수는 있겠음 => 한번만 나오는 경우를 빼면 됨
- 몇 번 등장하는지는 어떻게 셈?
- N / p => 애매함
- 애매한 이유는 7 이하에서 2가 몇번 나올까?
- 7 / 2 = 3 번? => 아님
- 2 x 1, 2 x 2, 2 x 3 => 4 번
- 7 : 2 x 1, 2 x 2, 2 x 3 => 2 * (1 ~ 3)
- 3 : 2 x 1
- 확장하면
- n : p x 1, p x 2, .... p x n1
- n1 : p x 1, p x 2, .... p x n2
- n2 : p x 1, p x 2, ... p x n3
- count(n, p) = n / p + count(n / 2, p)
- 이후 거듭제곱은 당연히 분할정복으로
newbieski