[백준 10986][파이썬] 나머지 합

https://www.acmicpc.net/problem/10986

10986번: 나머지 합

특정 수로 나누어 떨어지는 구간 합의 개수를 구하는 문제이다.

 

모든 (i, j)쌍을 구하면 너무 오랜 시간이 걸린다.

 

구간 합을 적절히 이용해서 효율적으로 답을 구하는 알고리즘을 짜야한다.

 

이 문제를 풀기 위해 우선 누적 합을 통해 구간 합을 구하는 방법을 알아야 한다.

 

백준 11659번 문제를 한 번 풀어보는 것을 추천한다.

 

https://growth-coder.tistory.com/91

 

이 문제를 풀기 위해서는 누적 합과 누적 합을 m으로 나눈 나머지를 알아야 한다.

인덱스	0	1	2	3	4	5
리스트	0	1	2	3	1	2
누적 합	0	1	3	6	7	9
누적 합%m	0	1	0	0	1	0

누적 합을 m으로 나눈 나머지를 구하는 이유는 나머지가 같은 것의 개수를 세기 위함이다.

 

먼저 A, B라는 수가 있고 이 두 수를 m으로 나눈 나머지가 n이라하자.

 

그러면 다음 식이 성립할 것이다.

 

 

A = a * m + n

B = b * m + n

 

그리고 B에서 A를 빼보면 

 

( B - A ) = ( b - a ) * m

 

( B - A )의 값은 m으로 나누어 떨어지는 수가 된다.

 

그리고 B와 A가 누적 합이었다면 (B-A)는 구간 합이 될테고 m으로 나누어 떨어지는 구간 합이 되는 것이다.

 

그래서 구간 합이 m으로 나누어 떨어지는 조건은 m으로 나누었을 때 나머지가 같은 두 개의 누적 합을 빼는 것이다.

 

그래서 이 문제는 곧 나머지가 같은 누적 합의 개수를 구하고 거기서 2개를 뽑는 경우의 수를 구하는 문제가 된다.

 

그러면 위에서 구한 누적 합을 m으로 나눈 나머지를 다시 보면

인덱스	0	1	2	3	4	5
누적 합%m	0	1	0	0	1	0

0이 4개, 1이 2개 이므로 다음 식의 값을 구하면 된다.

$$ 4C2 + 2C2 $$