Pigeonhole Principle (비둘기집 원리)

# 비둘기집 원리: 구간 합이 M 의 배수
def find_mod_zero_subarray(arr, m):
  first = {0: -1}  # prefix sum % m -> index
  pref = 0
  for i, x in enumerate(arr):
      pref = (pref + x) % m
      if pref in first:
          l = first[pref] + 1
          r = i
          return (l, r)  # arr[l..r] 합이 m 의 배수
      first[pref] = i
  return None
​
# 비둘기집 응용: 수열에서 같은 값의 두 원소
def has_duplicate(arr):
  return len(arr) != len(set(arr))
​
n, m = map(int, input().split())
a = list(map(int, input().split()))
res = find_mod_zero_subarray(a, m)
if res:
  l, r = res
  print(f"Found: [{l+1}, {r+1}]")
else:
  print("Not found (n < m)")

// 비둘기집 원리: 나머지 배열로 부분배열 합 M 의 배수 찾기
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      int n = Integer.parseInt(st.nextToken());
      int m = Integer.parseInt(st.nextToken());
      int[] a = new int[n];
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++)
          a[i] = Integer.parseInt(st.nextToken());
​
      int[] first = new int[m];
      Arrays.fill(first, -1);
      first[0] = 0;
      int sum = 0;
      for (int i = 0; i < n; i++) {
          sum = (sum + a[i]) % m;
          if (first[sum] != -1) {
              int l = first[sum] + 1, r = i + 1;
              System.out.println("Found: [" + l + ", " + r + "]");
              return;
          }
          first[sum] = i + 1;
      }
      System.out.println("Not found");
  }
}