[백준] 2247번(python 파이썬) - 실질적 약수

문제 링크: https://www.acmicpc.net/problem/2247

2247번: 실질적 약수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	1229	403	256	38.496%

문제

두 자연수 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)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 n이 주어진다.

출력

첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.

제한

• 1 ≤ n ≤ 200,000,000

 

 

 

 

풀이

---

이 문제를 풀면서 느낀 점은 정수에 대해 다른 사고를 가지지 못한다면 문제를 풀 수 없는 경우도 생길 수 있다는 것이었다.

 

생각하기가 너무 어려웠다. ㅜㅜ

 

일단 n의 범위가 2억까지 이므로 시간복잡도를 최대한 줄여야 한다.

 

보통 이 문제를 처음볼때 for문을 이용해 n까지 차근차근 약수들을 구해서 더할 것이다. 하지만 이러면 시간복잡도가

최소 O(n√n)이 걸린다. (n 의 실질적 약수를 구한다고 할때 2~ √n 까지 구하면 되기 때문)

 

 

그러면 어떤 생각을 해야할까...?

일단 이런 생각을 해보자

 

1~n 까지의 정수들 중에서 1~n 의약수를 가지는 것의 개수

ex) n = 16일때 1을 약수로 가진 것의 개수 16

      2를 약수로 가진것의 개수 8

      3을 약수로 가진것의 개수 5

      .....

      이렇게 가다보면 결국 i를 약수로 가진 것의 개수는 n//i 라는 것을 알 수 있다.

      

 

이 논리를 이용해 색다른 발상을 해보자

우리가 구할 것은 1부터 n 까지의 약수의 합이다. (실질적 약수말고 그냥 약수라고 쳐보자)

 

그렇다면 1 부터 n//2까지 +1씩 증가하는 수를 i라고 해보자

우리가 구하는 답 = (n//2) * i 이게 끝이다. (ㅋㅋㅋㅋ 너무 허무하다.) 

 

실질적 약수는 1과 자기자신을 제외해야하므로

2부터 시작하는 반복문에서 

          (n//2-1) * i 의 식으로 변환시키면 된다. 

 

사실 이렇게 구하는 것보다 더 빠르게 구하는 방식이 있다. 그것은 이 문제를 요청한 분에게 수기로 올려드렸다.

궁금하신 사람은 이 링크를 참고하길 바란다. 

 

https://ahgus89.github.io/algorithm/Harmonic-Lemma/

Harmonic-Lemma

 

사이트에는 n//i의 값이 똑같이 나오는 범위를 구할 수 있는 식이 증명되어있다.

이 식을 위에서 구한 야매(?) 코드와 섞으면 O(√n) 의 시간복잡도가 나온다. 

구현 코드

---

야매(?)코드

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

증명활용 코드

n = int(input())
answer = 0

for i in range(2, int(n**0.5) + 1):
    j = n // i
    ans += (j + i) * (j - i + 1) // 2
    ans += (j - i) * i

ans = ans % 1000000
print(ans)