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

解题思路:

   sum[i]表示前i项的和，如果（sum[j] - sum[i]）%k ==0（i<=j），即sum[i]%k==sum[j]%k,则区间[i+1,j]之和是k的倍数，然后用sum[i]=sum[i]%k,即前k项和模k的结果，用v[sum[i]]数组统计模k相等的个数
注意事项:

参考代码:

/*给定一个长度为N的数列，A1, A2, ... AN

如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数

我们就称这个区间[i, j]是K倍区间。

你能求出数列中总共有多少个K倍区间吗？*/

// (sum[i] - sum[j])%k==0  即 sum[i]%k = sum[j]%k 

#include<iostream>

using namespace std;

int main()

{

    int n,k;

    cin>>n>>k;

    long long sum[n+1],count=0;   //记录sum[i]%k 

    int v[k]={0};      //v[i]记录 sum[i]%k相等的个数 

    sum[0]=0;

    for(int i=1;i<=n;i++)

    {

        int temp;

        cin>>temp;

        sum[i] = (sum[i-1] + temp)%k;

        count += v[sum[i]];    //模k相等的数每多一个，就多v[sum[i]]个区间 

        //比如模K等于3的个数现在有5个，现在sum[i]又等于5，则k倍区间又多5个 

        v[sum[i]]++;    

    } 

    cout<<count+v[0]<<endl; //count只保留了区间开始位置不从1开始的，v[0]为所有下标从1开始的

    //即两个位置模K都等于0，之间也是k的倍数 

    return 0;

}