[C++][D4] 백준 1557번 제곱ㄴㄴ

https://www.acmicpc.net/problem/1557 짧길래 도전했다가 큰코 다친 문제였습니다 어떤 수 n이 주어졌을 때, n이하의 수 중에 제곱ㄴㄴ수가 아닌 수의 개수를 α라 하면, n이 몇번째 제곱ㄴㄴ수인지 계산하는 방법은 집합 A_i를 n>= i 인, i의 배수들의 집합이고, ex) n=10, A_4 = { 4, 8 } p_j를 j번째 소수의 값, m을 (p_k)^2 <= n 을 만족시키는 k의 최대값이라 하면, α는 다음과 같이 구할 수 있습니다. ( n(A) = 집합 A의 원소의 개수 ) ex) n=36, α = n(A_4 ∪ A_9 U A_25) = 36/4 + 36/9 + 36/25 - 36/(4*9) 결국 α는 소수의 배수들의 합집합의 개수인데 이런식으로 짝수개의 조합은 빼주고 홀수개의 조합은 더해주고 하면됩니다 (nC1-nC2+nC3-nC4 ... 이런식으로 쭉) 이제 n이 주어졌을때 몇번째 제곱ㄴㄴ수 인지 구한거고, 문제는 k가 주어졌을때 n을 구해야하...

원문링크 : [C++][D4] 백준 1557번 제곱ㄴㄴ