[알고리즘

(과제 5) 나머지 찾기

N개의 숫자 A1, A2,…, An이 주어지면 연속된 부분의 합이 M으로 나누어지는 간격의 수를 구하는 프로그램을 작성하십시오. 즉, Ai+…+…Aj(i<=j)의 합을 M으로 나누는 (i,j)-쌍의 수를 구합니다.

기입

첫 번째 줄에는 N과 M(1<=N<=106, 2<=M<=103)이, 두 번째 줄에는 N개의 숫자 A1,A2,...,An이 주어진다. (0<=AI<=109)

예제 입력

5, 3

1 2 3 1 2

샘플 출력

7

문제 분석

1)(A+B)%C는 ((A%C)+(B%C))%C와 같습니다. 특정 구간 수의 나머지 연산과 나머지 연산 값을 더한 값은 구간 합의 나머지 연산 값과 동일하다.

2) S(i)-S(j)는 원래 목록의 j+1에서 i까지 간격의 합입니다.

3) S(i)%M의 값과 S(j)%M의 값이 같다면 (S(i)-S(j))%M은 0이다.

손으로 해결

1) 목록 A의 합계로 구성된 배열 S를 만듭니다.

• 목록 A

• 합계 필드 S

2) 합계 필드에서 M(3) 나머지 연산을 수행합니다.

3) 경우의 수 계산

• 0:3의 요소 값 수
• 나머지 값이 같은 경우: 1은 2, 0은 3

4) 최종 결론

3 + 2C2 + 3C2 = 7

암호

import sys
input = sys.stdin.readline
n, m=map(int,input().split())
A=list(map(int,input().split()))
S=(0)*n
C=(0)*m
S(0)=A(0)
answer=0

for i in range(1,n)
	s(i)=s(i-1)+A(i)

for i in range(n):
	remainer =S(i)%m
    if remainer ==0:
    	answer+=1
    C(remainer)+=1

for i in range(m):
	if C(i) >1:
    	answer +=(C(i)*(C(i)-1)//2)

print(answer)

연습 코드

n=5
m=3

A=(1,2,3,1,2)

S=(0)*n
C=(0)*m #나머지로 올 수 있는 값은 0,1,2 로 m과 동일함
print(S)
print(C)
S(0)=A(0)
answer=0
print(S) #(1,0,0,0,0)

for i in range(1,n):
  S(i)=S(i-1)+A(i)

print(S) #(1,3,6,7,9) 합 배열 저장

for i in range(n):
  remainer=S(i)%m
  if remainer ==0:
    answer += 1
  C(remainer) += 1  
print(answer) #3
print(C) #(3,2,0) 나머지가 0인경우 3, 1인경우 2, 2인 경우 0

for i in range(m):
  if C(i) > 1:
    answer +=C(i)*(C(i)-1)//2

print(answer) #7