백준 10986번 [나머지 합]

구간 합 + 나머지(mod)

 

배열 + 합 ㅡ> 구간 합 저장

나머지 ㅡ> (A + B) % C = ((A%C) + (B%C)) % C

ll arr[1000001] = { 0, };
ll idx[1001] = { 0, };

ll combination(ll x) {
	if (x == 1) return 1;
	return (x * (x - 1)) / 2;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	ll res = 0;

	ll n, m;
	cin >> n >> m;
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		arr[i + 1] = (arr[i] + x)%m;
		idx[arr[i + 1]]++;
	}

	for (ll i = 1; i <= n; i++) {
		if (arr[i] == 0) res++;
	}

	for (ll i = 0; i <= 1000; i++) {
		if (idx[i] > 1) {
			res += combination(idx[i]);
		}
	}

	cout << res;

	return 0;
}