[BOJ/2247] 실질적 약수

문제 설명

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

2247번: 실질적 약수

문제 해결

 이 문제를 풀기 위해 많은 고민을 했는데 생각보다 쉽게 풀리는 문제였다.

O(sqrt(n)) 내에 풀리는 풀이도 있는 것 같은데 내가 푼 방법은 O(n) 내에 풀리는 방법이다.

 

 우선 실질적 약수라는 것은 어떤 수 N의 약수들 중 1과 N을 제외한 모든 약수를 의미한다. 실질적 약수의 합은 곧 그 약수들의 합이 된다. 실질적 약수를 구하기 위해서는 N을 2부터 sqrt(N)까지 나누어 일일히 확인하는 방법이 있다. 그러나 그 방법을 사용하면 약 2억개의 숫자에 대해 O(sqrt(N))의 연산을 진행해야 한다. 이 방법은 좋지 않다고 생각했다.

 

 아예 다른 접근 방법으로는 다음 방법을 사용했다.

1. 결국 필요한 건 약수들의 합이다.
2. 어떤 수 N의 약수 집합은  ${1, 2, 3, ..., N-K, N}$ 이런 형태로 이뤄져 있을 것이다.
3. 1 부터 N까지 어떤 수 X의 배수의 개수의 값은 $N // X$ 이다.
4. $(N // X)$ 에 X를 곱해주면 (배수의 개수) * (X값) 이다.

 예를 들어 1부터 10까지의 실질적 약수를 구하고 싶다고 가정하자.

 

X가 2라면, 1부터 10까지의 2의 배수의 개수는 5개이다. 5 * 2를 하면 2에 대한 실질적 약수의 합을 구할 수 있다.

단, 2의 실질적 약수는 없기 때문에 5 * 2에서 2를 빼야한다.

X가 3이면, 1부터 10까지의 3의 배수의 개수는 3개이다. 3 * 3 - 3을 하면 3에 대한 실질적 약수의 합을 구할 수 있다.

...

X가 5이면, 1부터 10까지의 5의 배수의 개수는 2개이다. 5 * 2 - 5를 하면 5에 대한 실질적 약수의 합을 구할 수 있다.

 

그런식으로 2부터 5까지의 모든 수에 대한 실질적 약수의 합을 구하면 된다.

코드

n = int(input())
cnt = 0
for i in range(2, n // 2 + 1):
    cnt += (n // i - 1) * i
print(cnt % 1000000)