알고리즘 문제 해설: 모듈로 합, 그래프 연결성 및 구간 쿼리
CF577B: Modulo Sum
주어진 수열에서 연속되지 않은 부분 수열을 선택하여 그 합이 특정 수 m으로 나누어 떨어지는지 판단하는 문제입니다.
해결의 핵심은 비둘기집 원리 (Pigeonhole Principle) 에 있습니다. 수열의 길이 n이 모듈로 값 m보다 크다면,PREFIX 합을 m으로 나눈 나머지는 총 m가지 경우しか 존재하지 않습니다. 따라서 n > m인 상황에서는 반드시 같은 나 ...
9월 17일 02:29에 게시됨