[Python] 백준 #2247 실질적 약수 - Gold 5
문제 링크
https://www.acmicpc.net/problem/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
인프런 강의(2주만에 통과하는 알고리즘 코딩테스트)에서 약수와 관련한 문제를 푸는 방식을 통해 풀게 되었다.
[정수 n까지의 실질적 약수의 합]
result = 0
for num in range(2, n//2 + 1):
result += num*(n//num - 1)예를 들어, n=100, num=2라면
2가 2부터 100까지의 짝수이지만, 2는 2의 실질적 약수가 아니므로 (100//2 - 1) 개가 있게 된다.
그러면 시간 복잡도가 O(n//2)=O(n)이 되므로 시간 초과가 안 뜰줄 알고 python으로 제출하니 시간 초과가 발생하였다 ㅠㅠ
그래서 우선 pypy으로 제출하니 되었다.
해결 방법 2
하지만, 이 문제는 충분히 python으로 제출해도 가능할거라 생각했다!
약수는 대칭을 이루는 수가 있다.
예를 들어, 6의 약수는 1,2,3,6 으로 1-6, 2-3 으로 짝지어진다.
따라서, n//2까지 반복을 하지 않고 sqrt(n)까지만 반복을 해도 해당하는 약수들만 잘 더하면 된다고 확신했다..
그런데, 그 수식을 계속 생각해봐도 떠오르지 않았다 ㅠㅠ
그래서 다른 블로그를 참고하였다!
https://sdev.tistory.com/1290
본 코드를 python에 맞게 변경하니 다음과 같았다.
for num in range(2, int(n**0.5) + 1):
k = n // num
result += num * (k - num + 1) + (k - num) * (k + num + 1) // 2
result %= 1000000이 또한 예시를 들어 설명하겠다.
예시로 n=10라고 해보자!
num * (k - num + 1)
num = 2라고 할 때,
10보다 작은 수에서 2를 약수로 가지고 있는 것은 2 * 1, 2 * 2, 2 * 3, 2 * 4, 2 * 5 5개(= k 개)이다.
이 때, 2 - 1 개(= num - 1 개)는 실질적 약수가 되지 못 한다.
따라서, 2 * ( 5 - 2 + 1) = 8 이다.
num = 3라고 할 때,
10보다 작은 수에서 3을 약수로 가지고 있는 것은 3 * 1, 3 * 2, 3 * 3 3개(= k 개)이다.
이 때, 6 = 2 * 3 = 3 * 2 에서 2의 대칭 약수로 이미 더하게 된다!
3 - 3 + 1개(=k - num + 1개)만 여기서 더해진다.
따라서, 3 * (3 - 3 + 1) = 3이다.
(k - num) * (k + num + 1) // 2
(대칭 되는 약수 개수) * (대칭 되는 약수들의 평균) 로 볼 수 있다.
num = 2라고 할 때,
[대칭 약수 개수]
4=2*2를 볼 때 2의 대칭 약수는 같은 2이므로 빼야한다.
따라서, (k - num + 1) - 1 = (k - num) 이 된다.
[ 대칭 약수]
이제 4를 제외한 2*3, 2*4, 2*5 에서 대칭 약수는 3,4,5가 된다!
이 뜻은, num+1부터 k까지가 대칭 약수가 된다는 것이다.
[대칭 약수들의 평균]
따라서, 그 대칭 약수들의 평균은 (k + num + 1) // 2 가 된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 2 | 2 | 2 | 2 | ||||||
| 3 | 4 | 5 |
num = 3라고 할 때,
3 * 3 보다 큰 수 중에 3을 약수로 갖는 수가 없어 0이 된다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 3 |
따라서 num = 10 일 때 결과는 (8 + 12) + (3) = 23이다.
또한, 시간 복잡도는 O(sqrt(n))이다.
최종 코드
import sys
input = sys.stdin.readline
def csod(n):
result = 0
for num in range(2, int(n**0.5) + 1):
k = n // num
result += num * (k - num + 1) + (k - num) * (k + num + 1) // 2
return result % 1000000
n = int(input())
result = csod(n)
print(result)