문제

수 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)

출력

첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다.

예제

입력
5 3
1 2 3 1 2

출력
7

나의 접근 방법

아이디어 생각하는게 관건이었던 문제
0 이상의 정수가 주어지기 때문에 누적합 배열이 계속해서 증가하는 형태를 띄고 있으므로 각 지점에서의 나머지를 미리 저장해놓으면 쉽게 풀 수 있다.
i번째 누적합의 나머지가 1이라고 했을 때 그 이전에 나머지가 1이었던 구간의 수만큼 result에 더해주면 된다.
예제의 경우를 보면 각 구간에서의 나머지가 1 0 0 1 0 인데 이를 토대로 계산을 해보면 다음과 같다.

  • 1번째 => 나머지가 1인 구간이 없으므로 result + 0
  • 2번째 => 나머지가 0인 구간이 없으므로 result + 0, 이 자체로 나머지가 0이므로 result + 1
  • 3번째 => 나머지가 0인 구간이 하나 있었으므로 result + 1, 이 자체로 나머지가 0이므로 result + 1
  • 4번째 => 나머지가 1인 구간이 하나 있었으므로 result + 1
  • 5번째 => 나머지가 0인 구간이 2개 있었으므로 result + 2, 이 자체로 나머지가 0이므로 result + 1

코드

#include<iostream>
#include<vector>
using namespace std;
int main(void){
  ios_base :: sync_with_stdio(false);
  cin.tie(NULL);
  long long N, M, result = 0;
  cin>>N>>M;
  vector<long long> sum(N+1);
  vector<int> remain(M+1);
  for(int i = 1 ; i<=N ; i++){
    cin>>sum[i];
    sum[i] += sum[i-1];
    long long r = sum[i] % M;
    if(r == 0) result++;
    result += remain[r];
    remain[r]++;
  }
  cout<<result;
  return 0;
}