풀이
(a[i] + ... + a[j]) % m = 0의 필요충분조건은
(a[1]+...+a[j]) % m = (a[1]+...+a[i-1]) % m이다.
오잉? 주어진 문제가 나머지가 x인 prefix sum의 개수를 k라고 할 때, k에서 2개를 고르는 경우의 수들의 합을 구하는 문제로 바뀌었다.
코드
#include <cstdio>
typedef long long ll;
int n, m, x;
ll r, s, a[1002]={1};
int main() {
scanf("%d %d", &n, &m);
while (n--) scanf("%d", &x), a[s=(s+x)%m]++;
while (m--) r+=(a[m]*(a[m]-1))/2;
printf("%lld", r);
return 0;
}
아무말
백준, 백준 온라인 저지, BOJ, Baekjoon Online Judge, C, C++, 씨, 씨쁠쁠, JAVA, algorithm, 자바, 알고리즘, 자료구조, 문제, 문제 풀이, 풀이