[蓝桥杯 2017 省 B] k 倍区间（前缀和+优化）

第一思路容易想到用前缀和数组，然后枚举可能出现的所有区间，对满足k倍区间的区间进行计数即可 #include<iostream> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int MAX=1e5+10; ll pre[MAX]; int n,k,ans=0; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ cin>>pre[i]; pre[i]=pre[i-1]+pre[i]; } for(int i=0;i<=n;i++){//注意变量范围 for(int j=i+1;j<=n;j++){ ll temp=pre[j]-pre[i]; if(temp%k==0){ ans++; } } } cout<<ans<<endl; return 0; } 不过对于该题的数据范围而言，O(n^2)的时间复杂度必然不够

那么应该怎么优化呢？？？ 我们先了解一下同余定理： 如果a，b除以c的余数相同，就称a，b对于除数c来说是同余的，且有a与b的差能被c整除．（a，b，c均为自然数） 例如，7，16除以3的余数相同都为1，就称7，16对于除数3来说是同余的，且7与16的差能被3整除。（7，16，3均为自然数） 据此我们就可以： 我们将所有的前缀和sum[i]全部模上K，统计所有相同余数的个数 根据上面的介绍，我们知道假设有m个前缀和满足除以K的余数相同，那么任意两个前缀和的差都能被K整除，所以K倍区间的个数就是，即m*(m-1)/2个 #include<iostream> #include<algorithm> #include<cmath> #define ll long long using namespace std; const int MAX=1e5+10; ll pre[MAX]; int n,k,ans=0; ll cnt[MAX]; int main(){ cin>>n>>k; for(int i=1;i<=n;i++){ int value; cin>>value; pre[i]=pre[i-1]+value; } for(int i=1;i<=n;i++){ int index=pre[i]%k; cnt[index]++;//对相同余数的前缀和进行计数 } for(int i=0;i<k;i++){ ans+=(cnt[i]*(cnt[i]-1)/2);//取组合数 } cout<<ans+cnt[0]<<endl;//注意最后还要加上本身就是k倍区间的前缀和 return 0; } 记得开long long