[백준] #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)을 구하는 프로그램을 작성하시오.

입력

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

출력

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

제한

1 ≤ n ≤ 200,000,000

예제

예제 입력 1
100
예제 출력 1
3150
예제 입력 2
2
예제 출력 2
0

---

풀이 과정

인프런 강의(2주만에 통과하는 알고리즘 코딩테스트 2강 - 정수론)에서 풀라고 제시 해주신 문제라 풀게 되었다.

푸는 것 자체는 문제가 안된다. 다만 시간 제한이 2초여서 단순하게 풀면 시간제한이 난다. 때문에 수학적 사고가 많이 필요해 어려웠다.
마지막쯤 가서는 구글링 하는 데도 나만 힘들어 하는 게 아니어서 다행이었다...ㅎㅎ;

특히 python으로는 시간초과 실패 나서 결국 pypy로 겨우 성공 시켰다.
채점하는 데만 2분 넘게 걸리더라.

고민하다가 결국 구글링 했는데 구글링 해도 나오는 글이 두 개 밖에 안보였음...ㅎㅋㅋㅋ
근데? 한 분은 내가 접근한 방법이랑 비슷하게 하셔서 참고했다.
마지막까지 고민했던 부분과 유사해서 ... 조금만 더 생각을 했으면, 혹은 다음에 와서 내가 스스로 이어서 풀면 풀 수 있었을까? 싶다.

우측 페이지 두줄 전까지는 내가 스스로 생각하면서 계산했던 부분이다. 참고한 내용과 비슷(같음)함. 진짜임ㅠ

근데 생각보다 너무 단순하게 짤 수 있어서 놀랐다.
어떻게 하면 이런 수학적 사고를 가질 수 있을까?😭

구현 코드

*python이 아닌 pypy로 제출해야 성공한다.

A = int(input())

temp_A = 0

for i in range(2, int(A/2+1)):
    temp_A+= i*(A//i -1) % 1000000

print(temp_A % 1000000)

• 참고한 곳
  올려주셔서 감사하다.
  수학적 증명을 이용하여 한 번 더 코드를 수정하신 부분이 있는데, 그 증명 부분은 읽지 못(안)했다. 다음에 여유있을 때 다시 보고 이해하고 넘어갈 것이다!
  

---

그리고 ...
주변에 코딩테스트 공부를 어떤 식으로 하냐 여쭤보니
1. 될 때까지 문제를 붙들고 고민하기
2. 시간을 정해서(보통 30분-2시간) 문제를 풀어보고 못 풀면 구글링
2번 방법으로 주로 공부하고 계신댔다. 지금 나는 1번 방법으로 공부 중인데... 시간도 많이 써야하는 것은 물론, 정신적으로도 힘든 것도 있다. 2번 방법으로 하다가 내 실력이 안 올라가면 어쩌지? 하는 것 때문에 고민 중이다. 어떻게 해야할까🤔🥲