[백준10986]나머지 합

입력

**첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103)

둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109)
**

출력

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

코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	long long n, m,sum;
	sum = 0;
	cin >> n >> m;
	long long arr[1001];
	long long  cnt = 0;
	for (int i = 1; i <= n; i++)
	{
		int temp;
		cin >> temp;
		sum += temp;

		arr[sum % m]++;
		if (sum % m == 0)
		{
			cnt++;
		}
	}
	for (int i = 0; i <= m; i++)
	{
		cnt += arr[i] * (arr[i] - 1) / 2;
	}
	//cout << arr[0]<<"\n"<<cnt<<"\n";
	cout << cnt;
 }

아이디어

-(a+b) % c는((a%b)+(b%c) %c 와 같다. 다시 말해 특정 구간 수들의
나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값은 동일하다.

-구간 합 배열을 이용한 식 arr[j]-arr[i]는 원본 배열의 i+1부터 j까지의 구간합이다.

-arr[j] % m의 값과 s[i] % m의 값이 같다면 (s[j]-s[i]) %m은 0이다.
즉 구간 합 배열의 원소를 m으로 나눈 나머지로 업데이트하고 arr[j]와 arr[i]가 같은 i,j쌍을 찾으면
원본 배열에서 i+1부터 j까지의 구간합이 m으로 나누어떨어진다는 것을 알 수 있다.