[백준] 10986번 나머지 합 - Python

풀이

접근방법

• 어떤 수 M로 나눴을 때, 나머지가 동일한 2개의 수의 차이를 M으로 나누면 나머지가 0이다.
• 예시로 1, 7은 3으로 나눴을 때 나머지가 1이다. 이 두 수의 차이는 6으로 이는 3으로 나누면 나머지가 0이다.
• A = a x M + C, B = b * M + C => A-B = (a-b) x M
• 주어진 문제에서 이 성질을 이용하면 구간의 합이 M으로 나눠 떨어지는 구간을 구할 수 있다.
• $A_i + \dots + A_j(i \leq j)$은 (j번째 까지의 누적합 - i-1번째 까지의 누접합)과 같다.
• 이 때 "j번째 까지의 누적합"과 "i-1번째 까지의 누적합", 둘 다 M으로 나눴을 때 나머지가 동일하다면 $A_i + \dots + A_j(i \leq j)$은 M으로 나눠 떨어질 것이다.
• 따라서 M으로 나눠 떨어지는 구간의 수를 구하려면 나머지가 동일한 누적합의 조합을 찾아야한다. 나머지 값이 동일한 누적합의 수를 계산한다.
• i(0~N-1)번째 까지의 누적합을 구하고, 누적합을 M으로 나눴을 때 나머지를 계산한다. 이 과정을 0~i-1번 째 까지 계산하며 나머지 값에 따른 누적합의 개수를 계산한다.(ex: 나머지가 0인 누적합의 수: 3개, 나머지가 1인 누적합의 수:2개)
• 나머지값에 따른 조합의 수는 나머지가 동일한 누접합의 갯수(n)에서 순서에 상관없이 2개를 뽑으면 되므로 ${}_{n}C_{2}$개의 경우의 수가 나온다. 이를 모든 나머지값에서(0 ~ M-1) 반복하면서 조합의 수를 다 더해준다.
• 0일 때는 그 자체가 M으로 나눠 떨어지는 구간이므로, 나머지가 0인 누접합의 수를 한 번 더 더해줘야 최종적으로 M으로 나누어 떨어지는 연속된 분 구간의 수가 나온다.

예제적용

• 3 + ${}_3C_{2}$ + ${}_2C_{2}$ = 7

코드

from sys import stdin
input = stdin.readline
N, M = map(int, input().split())
A = list(map(int, input().split()))
rem = [0] * M # 나머지값에 따른 누적합의 개수를 담는 리스트

cumsum = 0
for v in A:
    cumsum += v
    rem[cumsum % M] += 1

answer = 0
for v in rem:
    answer += v * (v-1) // 2 # nC2, 나머지 값에 따른 조합의 수
answer += rem[0] # 나머지가 0일 때, 한 번 더 더해주기
print(answer)