Boj 11692) 시그마함수

문제

백준 11692

방법 1

설명

\[\text{원래 수} = \text{약수} \times \text{어떤 수}\]

약수는 위처럼 표현할 수 있음.

홀수인 약수의 갯수로 약수의 합이 홀짝인지 알 수 있기 때문에 홀수인 약수가 나오는 경우를 살펴봐야함.

약수가 홀수인 경우는

\[\begin{multline} \text{원래 수} = 2^x \times \text{홀수} \\ \shoveleft = \text{약수} \times 2^x \times \text{어떤 홀수} \\ \shoveleft \end{multline}\]

여기서 원래수가 홀수여야만 짝이 되는 약수도 홀수가 되는 것 을 알 수 있음.

짝수는 합의 홀짝과는 관계가 없기 때문에 원래수를 2의 거듭제곱수로 나눠서 약수의 합을 구해도 홀짝에는 관계가 없음 .

그리고 원래수가 홀수일 때 약수의 짝이 존재하는 경우(약수의 거듭제곱이 원래수가 아닌경우) 홀짝과 무관함 을 알 수 있음. 왜냐하면 홀수+홀수는 짝수이기 때문임.

그러면 약수의 합이 홀수인 경우는 다음과 같음

\[\text{원래 수} = (\text{홀수})^2 \times 2^x\]

그럼 위의 코드가 이해가 됨

시간 복잡도

O(LogN)

코드

using INT = int64_t;

int main()
{
	INT n;
	cin >> n;

	// 2 다 빼고, 제곱수면 약수합이 홀수
	// => sqrt 에서 홀수 + 여기서 2 곱해서 원래수 이하되는 수
	// => sqrt(n) 홀수 + sqrt(n/2) 의 홀수 + sqrt(n/4) 의 홀수
	
	INT ans = n;
	while (n > 0)
	{
		ans -= ((INT)sqrt(n)+1)/2;
		n /= 2;
	}
	cout << ans;
}

방법2

설명

\[\begin{multline} \text{원래 수} \\ \shoveleft = (\text{홀수})^2 \times 2^x \\ \shoveleft = \begin{cases} (\text{수})^2 \\ (\text{수})^2 \times 2 \\ \end{cases} \end{multline}\]

위에서 알게된 위 식은 두가지 경우가 가능함.

즉 제곱수거나 제곱수에 2 곱한 값임.

그대로 전체 수에서 빼주면 됨.

시간 복잡도

O(1)

코드

using INT = int64_t;

int main()
{
	INT n;
	cin >> n;
	cout << n - (INT)sqrt(n) - (INT)sqrt(n/2);
}