백준 10986번 : 나머지 합 [C#]

1. 모든 경우의 수를 계산하면 N제곱 > 10만의 제곱으로 너무 오래걸린다.

2. 구간 [i,j]의 합은  구간[ 0, j ]의 합 - 구간[ 0, i ]의 합이기도 하다.

3. ( 구간[ 0, j ]의 합 - 구간[ 0, i ]의 합 )이 M으로 나누어 떨어진다는 것을 수식으로 나타내면

4. 이 수식에서 분배법칙으로 변형하면

두 구간의 합을 M으로 나눈 나머지가 같다는 결과를 얻을 수 있습니다.

 

5. 0번부터 N-1번까지 더해가며 구간의 합을 구하고, M으로 나눈 나머지의 값을 항목마다 갯수를 새샙니다.

6. 나머지가 0인 구간은 최종값에 더하고, 각 구간에서 전체중에 순서 상관없이 2개를 뽑는 콤비네이션을 돌려 최종값에 더합니다.

> nC2 = ( n*(n-1) ) /  2 입니다.

 

using System.Numerics;
using System.Text;

class Program
{

    static void Main()
    {
        string[] s = Console.ReadLine().Split();

        int N = int.Parse(s[0]);
        int M = int.Parse(s[1]);
        
        s = Console.ReadLine().Split();

        long sum = 0;
        long[] remain = new long[M+1];

        for(int i=0; i<s.Length; i++)
        {
            int n = int.Parse(s[i])%M;
            sum+= n;

            remain[ ( sum%M ) ]++;
        }

        long ans = 0;

        ans+= remain[0]; // 0번부터의 합이 M으로 나누어 떨어지는 구간의 수

        for(int i=0; i<M; i++)
        {
            if (remain[i] > 1)
            {
                ans += (remain[i] * (remain[i]-1) )/2;
            }
        }

        Console.Write(ans);
    }
}