์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๊ตฌ๊ฐ„ํ•ฉ ์ •์˜ : i ~ j ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ = (1~ j ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) - (1 ~ i -1 ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ)

  • ์œ„ ์ •์˜์— ๋”ฐ๋ผ ์šฐ๋ฆฌ๊ฐ€ ๊ตฌํ•ด์•ผํ•˜๋Š” (i ~ j ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) % m = 0 ์€

    ((1~ j ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) % m - (1 ~ i -1 ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) % m) % m ๊ณผ ๊ฐ™์Œ

  • ๋”ฐ๋ผ์„œ (1~ j ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) % m = (1 ~ i -1 ๊นŒ์ง€์˜ ๊ตฌ๊ฐ„ํ•ฉ) % m ์ธ (i, j) ๊ฐ€ ์กฐ๊ฑด์„ ๋งŒ์กฑํ•จ.

์ฝ”๋“œ

#include <iostream>
 
typedef long long ll;
using namespace std;
 
int n, m, num[1000100], save[1100];
ll sum[1000100];
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n >> m;
	cin >> num[0];
	sum[0] = num[0];
	for (int i = 1; i < n; i++) {
		cin >> num[i];
		sum[i] = sum[i - 1] + num[i];
	}
 
	save[0] = 1;
	for (int i = 0; i < n; i++)
		save[sum[i] % m]++;
 
	ll cnt = 0;
	for (int i = 0; i < m; i++) {
		ll x = save[i] -1;
		cnt += (x * (x + 1) / 2);
	}
	cout << cnt;
}