์๊ณ ๋ฆฌ์ฆ
-
๊ตฌ๊ฐํฉ ์ ์ : 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;
}