算法1

前缀和，统计模k不同值的前缀和，再用组合数统计一下结果

#include<cstdio>
#include<cstring>
using namespace std;

typedef long long LL;

const int N = 100010;

LL cnt[N];

int n, k;

int main()
{
    scanf("%d%d", &n, &k);
    LL prefix = 0;
    for(int i = 1; i <= n; ++ i)
    {
        LL a;
        scanf("%lld", &a);
        prefix += a;
        cnt[prefix % k] ++;
    }
    //for(int i = 0; i < k; ++ i) printf("%d ", cnt[i]);
    cnt[0] ++;
    LL res = 0;
    for(int i = 0; i < k; ++ i)
        if(cnt[i])
            res += cnt[i] * (cnt[i] - 1) / 2;
    printf("%lld", res);
    return 0;
}