問題

https://beta.atcoder.jp/contests/abc105/tasks/abc105_d

数列 $A$ が与えられる。閉区間 $[A_l + A_{l+1} + ... + A_r ]$ の和が $M$ の倍数になる区間の個数を求めよ。

考え方

$[A_l + A_{l+1} + ... + A_r ]$ の累積和を $B_r - B_{l-1}$ とする。これが $M$ の倍数になる時 $B_r$ と $B_{l-1}$ が $M$ の倍数でなければなりません。よって $A$ の累積和をとり、 $M$ であまりをとったときに、同じ値の数から $2$ つ選ぶときの組み合わせの個数が解になります。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            int n = in.nextInt();
            long m = in.nextLong();
            long[] a = new long[n+1];
            long[] sum = new long[n+1];
            Map<Long, Long> map = new HashMap<>();
            for (int i = 1; i < n+1; i++) {
                a[i] = in.nextLong();
                sum[i] = sum[i-1] + a[i];
                sum[i] %= m;
            }
            for (long l : sum) {
                map.merge(l, 1L, Long::sum);
            }

            long ans = 0;
            for (long l : map.keySet()) {
                long v = map.get(l);
                if (v >= 2) {
                    ans += v * (v-1) / 2;
                }
            }
            out.println(ans);
        }