백준 2247 C++

백준 2247

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다.

실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다.

SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1) + SOD(2) + … + SOD(n)이라고 하자.

CSOD(n)을 구하는 프로그램을 작성하시오.

풀이

이거를 보이는대로 2억번 돌려가면서 풀려고 하면, 2억번을 돌면서 그 안에서도 또 약수를 구하기에 시간초과가 뜨고만다. 그렇기에 생각을 바꿔서 약수를 구하지말고, 나누려는 수의 배수의 갯수를 구하는 게 방법이다.

for문을 구하는건 똑같은데, 한 N이라는 수가 있다면 N/2까지만 자기 자신을 제외한 약수가 있으니까 for문 도는거의 끝은 N/2까지만 돈다.

N이 10이라고 가정해보자.

div가 2일때

ans += 8

div가 3일때

ans += 6

div가 4일때

ans += 4

div가 5일때.

ans += 5

… 즉 보면 1과 자기 자신을 제외한 div의 배수가 몇 개가 들어가는지 찾고, 그 배수의 갯수 * div를 계속 N/2까지 더해주면 그게 여기서 구하려는 실질적 약수의 합이다.

#include <iostream>
#include <algorithm>


using namespace std;

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

	long long N, ans = 0;
	cin >> N;
	for (int div = 2; div <= (N / 2); div++) {
		ans += (div * ((N / div) - 1)) % 1000000;
		ans %= 1000000;
	}
	cout << ans;
	return 0;
}

BOJ 카테고리 내 다른 글 보러가기