누적합

문제는 다음과 같다. 문제의 핵심은 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값을 동일하다. 구간 합 배열을 이용한 S[j] - S[i]는 원본 배열의 i+1 부터 j까지의 구간 합이다. S[j] % M의 값이 같다면 (S[j] - S[i]) % M 은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i,j)쌍을 찾으면 원본 배열에서 i+1부터 j까지의 구간 합이 M으로 나누어 떨어진다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..
말동말동현
'누적합' 태그의 글 목록