[TIL #18] 약수의 개수와 덧셈

두 정수 $n$과 $m$이 주어진다.

둘 사이의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고,

개수가 홀수인 수는 뺀 수를 리턴해야 한다.

 

약수문제? 반복문으로 브루트 포스 하듯이 할 수도 있지만...

이미 수의 성질을 활용해 여러 문제를 해결하지 않았는가.

여기서도 활용할 수 있다.

 

어떤 자연수 $n$의 약수의 개수가 짝수인지 여부를 확인하려면,

해당 자연수가 완전 제곱수인지 확인하면 된다.

 

자연수의 약수는 짝을 이루어 나타난다.

$n = 12$의 경우, 약수는 $1, 2, 3, 4, 6, 12$이고, 짝을 이루는 것을 확인할 수 있다.

하지만 완전 제곱수일 경우, 예를 들어 $n = 16$일 때 약수는 $1, 2, 4, 8, 16$이다.

4가 2번 등장하게 되므로 하나의 수로 취급하게 되어 약수의 개수가 홀수가 된다.

따라서 완전 제곱수를 판별하기 위해선 $\sqrt{n}$이 정수인지 확인하면 된다.

 

위 내용을 코드로 작성하면 다음과 같다.

#include <cmath>

using namespace std;

int solution(int left, int right) {
    int answer = 0;
    
    for (int num = left; num <= right; num++) {
        int sqrtN = sqrt(num);
        
        if (sqrtN * sqrtN == num)
            answer -= num;
        else
            answer += num;
    }        
    
    return answer;
}

완전 제곱수인지 확인하기 위해 구한 제곱근을 다시 제곱했다.

제곱근이 정수가 아니라면 ``int``에 저장 시 소수점은 사라지기 때문에 판별할 수 있다.