https://www.acmicpc.net/problem/1215
k가 37인 경우를 보면,
첫째, k // i의 값이 37, 18, 12, 9,7, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 인데,
이 값과 나머지 값의 패턴이 상관있어 보임.
둘쨰, 피크를 이루다가 감소하는 구간에서 감소하는 기울기는 그 구간의 k//i 값임.
셋째, k // i의 값의 구간별 변화량을 보면 아래와 같은데, 이것은 반대편 구간의 길이와 같음. 즉, 구간 시작 구간의 i의 개수와 같음. (마지막은 0으로 간주)
| 1 × 37 | 2 × 18 | 3 × 12 | 4 × 9 | 5 × 7 | 6 × 6 | 7 × 5 | 9 × 4 | 12 × 3 | 18 × 2 | |
| i | 1 →2 | 2 →3 | 3 →4 | 4 →5 | 5 →6 | 6 →7 | 7 →8 | 9 →10 | 12 →13 | 18 →19 |
| 37→18 | 18→12 | 12 →9 | 9 →7 | 7 →6 | 6 →5 | 5 →4 | 4 →3 | 3 →2 | 2 →1 | |
| 변화량 | 19 | 6 | 3 | 2 | 1 | 1 | 1 | 1 | 1 | 1 |
| 1 의 개수 |
2의 개수 |
3의 개수 |
4의 개수 |
5의 개수 |
6의 개수 |
7의 개수 |
9의 개수 |
12의 개수 |
18의 개수 |
반비례 그래프라고 생각할 수 있는데 그렇다면 $/sqrt{i}$까지 계산하면 전 구간을 알 수 있다.
N, K = map(int, open(0).readline().split())
i = 2
prev = K
total = 0
if N > K:
total += (N - K) * K
sqrt_K = int(K**0.5)
while K // i > sqrt_K:
curr = K // i
if curr < N <= prev:
cnt = N - curr
total += cnt * (K % N + K % (curr + 1)) // 2
elif N > prev:
cnt = prev - curr
total += cnt * (K % prev + K % (curr + 1)) // 2
prev = curr
i += 1
if prev > N:
prev = N
while prev:
total += K % prev
prev -= 1
print(total)1. 기본 입력 처리 및 초기 변수 설정
우선, 코드에서 N과 K를 입력받고, 몇 가지 변수를 초기화합니다.
N, K = map(int, open(0).readline().split())
i = 2
prev = K
total = 0
N,K: 문제에서 주어지는 두 정수입니다.i: 나누기 연산의 인덱스 역할을 하는 변수입니다.prev: 이전 나누기 결과를 저장하는 변수입니다.total: 나머지의 합을 저장하는 변수입니다.
2. N이 K보다 큰 경우 처리
만약 N이 K보다 크다면, N에서 K까지의 모든 수에 대해 나머지는 K가 됩니다. 따라서 아래와 같이 처리합니다.
if N > K:
total += (N - K) * K
여기서 (N - K) * K는 N에서 K까지 모든 수의 나머지를 더하는 것입니다. 예를 들어, N = 10이고 K = 5일 때, 6, 7, 8, 9, 10에 대한 나머지는 모두 K입니다.
3. 효율적인 나머지 계산을 위한 루프
다음으로, 나머지를 효율적으로 계산하기 위해 K의 제곱근까지만 반복합니다. 이는 시간 복잡도를 줄이기 위해 중요한 부분입니다. 이 과정은 아래와 같습니다.
sqrt_K = int(K**0.5)
while K // i > sqrt_K:
curr = K // i
if curr < N <= prev:
cnt = N - curr
total += cnt * (K % N + K % (curr + 1)) // 2
elif N > prev:
cnt = prev - curr
total += cnt * (K % prev + K % (curr + 1)) // 2
prev = curr
i += 1
sqrt_K:K의 제곱근입니다. 이는 나머지 계산의 범위를 줄이기 위해 사용됩니다.while K // i > sqrt_K:K를i로 나눈 값이sqrt_K보다 클 때까지 반복합니다.
제곱근까지만 반복하는 이유
제곱근까지만 반복하는 이유는 효율성 때문입니다. 나누기 연산에서 몫이 동일하게 유지되는 구간을 그룹화하여 계산하면 중복 계산을 피할 수 있습니다. 예를 들어, K = 1000인 경우, K // 1부터 K // 31까지의 결과는 고유하지만, 그 이후로는 결과가 반복되기 시작합니다.
즉, K // i에서 i가 증가함에 따라 몫이 변하지 않는 구간들이 생기고, 이 구간들을 묶어서 처리하면 계산량을 크게 줄일 수 있습니다. 이를 통해 시간 복잡도를 O(sqrt(K))로 줄일 수 있습니다.
루프 내에서는 다음을 수행합니다:
curr = K // i: 현재K를i로 나눈 값을 계산합니다.cnt: 현재 구간의 길이를 계산합니다.total에 나머지의 합을 더합니다.
여기서 수학적 원리는 K를 i로 나눈 몫이 변하는 지점을 기준으로 나머지를 그룹화하여 효율적으로 합산하는 것입니다.
4. 남은 나머지 계산
루프가 끝난 후, prev가 N보다 크다면 prev를 N으로 설정하고, 남은 나머지를 모두 더합니다.
if prev > N:
prev = N
while prev:
total += K % prev
prev -= 1
이 부분에서는 남은 모든 수에 대해 나머지를 계산하여 total에 더합니다. 이를 통해 모든 나머지의 합이 완성됩니다.
k가 37일 때의 값들을 기반으로 구간 계산을 설명하겠습니다.
- 기본 변수 설정 및 입력 처리
N, K = 40, 37 # 예시 입력값
i = 2
prev = K
total = 0
- N이 K보다 큰 경우 처리
N이 K보다 크므로 (N - K) * K를 더합니다.
if N > K:
total += (N - K) * K
total += (40 - 37) * 37 # total = 3 * 37 = 111
- 효율적인 나머지 계산을 위한 루프
sqrt_K = int(K**0.5) # K의 제곱근, sqrt_K = 6
while K // i > sqrt_K:
curr = K // i # 현재 K를 i로 나눈 값
if curr < N <= prev:
cnt = N - curr
total += cnt * (K % N + K % (curr + 1)) // 2
elif N > prev:
cnt = prev - curr
total += cnt * (K % prev + K % (curr + 1)) // 2
prev = curr
i += 1
이 부분을 구체적으로 계산해보겠습니다.
- 첫 번째 루프 (i = 2)
curr = K // i # curr = 37 // 2 = 18
cnt = prev - curr # cnt = 37 - 18 = 19
total += cnt * (K % prev + K % (curr + 1)) // 2
total += 19 * (37 % 37 + 37 % 19) // 2
total += 19 * (0 + 18) // 2
total += 171 # total = 111 + 171 = 282
prev = curr # prev = 18
i += 1 # i = 3
- 두 번째 루프 (i = 3)
curr = K // i # curr = 37 // 3 = 12
cnt = prev - curr # cnt = 18 - 12 = 6
total += cnt * (K % prev + K % (curr + 1)) // 2
total += 6 * (37 % 18 + 37 % 13) // 2
total += 6 * (1 + 11) // 2
total += 36 # total = 282 + 36 = 318
prev = curr # prev = 12
i += 1 # i = 4
- 세 번째 루프 (i = 4)
curr = K // i # curr = 37 // 4 = 9
cnt = prev - curr # cnt = 12 - 9 = 3
total += cnt * (K % prev + K % (curr + 1)) // 2
total += 3 * (37 % 12 + 37 % 10) // 2
total += 3 * (1 + 7) // 2
total += 12 # total = 318 + 12 = 330
prev = curr # prev = 9
i += 1 # i = 5
- 네 번째 루프 (i = 5)
curr = K // i # curr = 37 // 5 = 7
cnt = prev - curr # cnt = 9 - 7 = 2
total += cnt * (K % prev + K % (curr + 1)) // 2
total += 2 * (37 % 9 + 37 % 8) // 2
total += 2 * (1 + 5) // 2
total += 6 # total = 330 + 6 = 336
prev = curr # prev = 7
i += 1 # i = 6
- 다섯 번째 루프 (i = 6)
curr = K // i # curr = 37 // 6 = 6
cnt = prev - curr # cnt = 7 - 6 = 1
total += cnt * (K % prev + K % (curr + 1)) // 2
total += 1 * (37 % 7 + 37 % 7) // 2
total += 1 * (2 + 2) // 2
total += 2 # total = 336 + 2 = 338
prev = curr # prev = 6
i += 1 # i = 7
- 남은 나머지 계산
if prev > N:
prev = N
while prev:
total += K % prev
prev -= 1
여기서는 prev가 6이기 때문에 남은 값을 모두 더합니다.
total += 37 % 6 # total += 1 # total = 338 + 1 = 339
total += 37 % 5 # total += 2 # total = 339 + 2 = 341
total += 37 % 4 # total += 1 # total = 341 + 1 = 342
total += 37 % 3 # total += 1 # total = 342 + 1 = 343
total += 37 % 2 # total += 1 # total = 343 + 1 = 344
total += 37 % 1 # total += 0 # total = 344 + 0 = 344
이렇게 하여 total 값은 344가 됩니다.
이 과정은 K를 i로 나누면서 몫이 변하는 구간을 기준으로 계산하여 효율적으로 나머지를 더하는 방식입니다. 구간별 변화량을 통해 중복 계산을 피하고, 시간 복잡도를 줄이는 것이 핵심입니다.