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

解题思路:

注意事项:

1、数据比较多（n=1e5）,建议用scanf读入

2、最坏的情况前缀和是10万的平方，1e10,int最多2x10^9，开long long,ans也是

3、时间复杂度->o(n^2)约为1e10超限

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

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

        {

            sum=s[j]-s[i-1];

            if(sum%k==0)

            ans++;

        }

参考代码:

#include<iostream>

using namespace std;

typedef long long LL;

const int N=100010;

LL s[N],cnt[N],res;

int n,k;

int main()

{

    cin>>n>>k;

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

    {

        cin>>s[i];

        s[i]=s[i-1]+s[i];

    }

     cnt[0]=1;//就是我们这样做我们少计算了区间[0,i]构成的k倍区间，其个数为cnt[0]=1，故加上。

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

    {

        cnt[s[i]%k]++;  

    }

      for(int i = 0; i < k; i++) { //余数必然在0~k-1之间

        res += cnt[i] * (cnt[i] - 1) / 2;//Cn2就是要选两个前缀和相减,n(n-1)/2

    }

    cout<<res<<endl;

}