취미로 코딩하기

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

이번에 볼 문제는 백준 2247번 문제인 실질적 약수이다.
문제는 아래 링크를 확인하자.

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

CSOD(N)은 계산순서를 바꿔 각 2 이상의 k에 대하여 (N 이하의 (k가 아닌) k의 배수의 개수) * k 들의 합으로 계산해낼 수 있다는 점을 관찰하자.

각 k에 대하여 위의 식의 값을 계산하는 방법이 복잡하지 않고 N의 범위가 2억 이하이며 시간제한 또한 2초이므로, 위의 값을 반복문을 돌려 직접 계산해 문제를 해결하자. 별다른 최적화 없는 아래와 같은 코드로도 문제를 충분히 해결할 수 있다.

다른 수와 다르게 1은 특히 "1과 자기자신을 제외"하는 부분을 구현할 때 예외처리할 부분이 생길 수 있는 점에 유의하여 구현하자.

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

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

ll N, ans;

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

	cin >> N;
	
	if (N == 1) {
		cout << 0;
		return 0;
	}

	for (ll i = 2; i < N; i++) {
		ans += (N / i) * i;
	}

	cout << (ans - N * (N - 1) / 2 + 1) % 1000000;
}