[BOJ 11692 // C++] 시그마 함수

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 11692번 문제인 시그마 함수이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/11692 

11692번: 시그마 함수

 

양의 정수 \(n\)이 \(p_1^{k_1} p_2^{k_2}\cdots p_m^{k_m}\)으로 소인수분해될 때, \(n\)의 양의 약수의 합은 \((1+p_1+p_1^2+\cdots +p_1^{k_1}) (1+p_2+p_2^2+\cdots +p_2^{k_2})\cdots (1+p_m+p_m^2+\cdots +p_m^{k_m})\)과 같이 나타낼 수 있음을 기억해내자. (중학교 교육과정)

 

홀수인 소수 \(p\)에 대하여 \(1+p+p^2+\cdots +p^{k}\)의 값은 \(k\)의 값이 홀수일 때 짝수가 되고 짝수일 때 홀수가 된다. 그리고 \(p=2\)인 경우 \(1+p+p^2+\cdots +p^{k}\)의 값은 항상 홀수가 된다.

 

따라서 \(n\)의 양의 약수의 합은 \(n\)이 (제곱수) 또는 (제곱수)*2꼴의 수일 때 홀수, 그 외의 경우 짝수가 됨을 알 수 있다.

 

한편 \(n\) 이하의 제곱수의 개수는 \(O(\sqrt{n})\)개 있으므로, \(10^{12}\) 이하의 각 제곱수와 그 2배 꼴의 수에 대하여 \(n\) 이하인지 하나하나 확인해 문제를 해결할 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll N;
ll cnt;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (ll i = 1; i < 1000001; i++) {
		if (i * i <= N) cnt++;
		if (i * i * 2 <= N) cnt++;
	}

	cout << N - cnt;
}