취미로 코딩하기

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

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

https://www.acmicpc.net/problem/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;
}