第八届 压轴 k倍区间

//超时做法 暴力 过 99%
# include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n, k;
long long cnt[N], s[N], b[N];

int main()
{
    long long res = 0;
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    if(s[1] % k ==0) res ++;
    for(int i = 0; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++)
        {
            if( (s[j] - s[i]) % k == 0) res ++;
        }
    }
    cout << res;
    return 0;
}

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int n, k;
ll cnt[N], s[N];

int main(void)
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; i++)
    {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }
    ll ans = 0;
    cnt[0] = 1; // 我们默认第一个位置(s[0]) 有数(0%k==0), 所以初始化cnt[0]=1;
    for(int r = 1; r <= n; r++)
    {
        ans += cnt[s[r] % k];
        cnt[s[r] % k]++;
    }
    printf("%lld\n", ans);
    return 0;
}