蓝桥杯2017年第八届真题-k倍区间 前缀和

解题思路:

#include <iostream>
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

ll n, k;
ll a[N], cnt[N];

int main()
{
    cin >> n >> k;
    
    for (int i = 1; i <= n; i ++ ){
        
        scanf("%d",&a[i]);
        a[i] += a[i - 1];
    } 
    
    ll res = 0;
    
    for (int i = 1; i <= n; i ++ )
    {
        res += cnt[a[i] % k];
        if (a[i] % k == 0) res ++ ;
        cnt[a[i] % k] ++ ;
    }
    cout << res;
}

注意事项:

参考代码: