[백준] 13909 창문닫기 C++

문제 입력 첫 번째 줄에는 창문의 개수와 사람의 수 N(1 ≤ N ≤ 2,100,000,000)이 주어진다. 출력 마지막에 열려 있는 창문의 개수를 출력한다. 문제 링크 분석 결론부터 말한다면 N개보다 작거나 같은 제곱수의 개수를 세는 문제이다. 최종적으로는 창문이 열려있는 개수를 세면 된다. 다만 창문과 사람의 수에 볼드처리가 되어있는 것에서 알 수 있듯이. 실제로 각 배수마다 창문을 열고 닫으면 시간초과가 날 것이다. 때문에 최종적으로 창문이 열릴 조건을 찾아내는 것이 핵심이다. 창문이 최종적으로 열려 있으려면 처음에는 닫혀 있으므로 열고닫는 횟수가 홀수면 된다. 각 창문이 열고 닫히는 횟수는 해당하는 수의 약수의 개수와 동일하다. Ex. 4번째 창문을 열고닫는 사람은 1번째, 2번째, 4번째 사람 ..

2023.09.26