蓝桥杯-k倍区间 | 模的应用

2019-04-13 20:42发布

K倍区间

问题描述
  给定一个长度为N的数列,A1, A2, … AN,如果其中一段连续的子序列Ai, Ai+1, … Aj(i <= j)之和是K的倍数,我们就称这个区间[i, j]是K倍区间。
  你能求出数列中总共有多少个K倍区间吗? 输入格式
  第一行包含两个整数N和K。(1 <= N, K <= 100000)
  以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出格式
  输出一个整数,代表K倍区间的数目。
样例输入
5 2
1 2 3 4 5
样例输出
6 思路: 暴力两遍for循环的时间复杂度是O(n^2),肯定会超时。区间和一般会用前缀和或者后缀和处理一遍,这样一遍下来才O(n)。接下来就是处理 k的倍数的问题。求前缀和的同时取模,这样模数为0的就是满足条件的答案。
( y-x )%k==0 <==> y%k-x%k==0 , 可以得出结论,相同模数的区间一定是k的倍数
如果模数为d的有 t 个,那么这样的区间就是 t(t1)2" role="presentation">t(t1)2。注意这里相乘会爆int最后的答案就是 i=0k1ci(ci1)2" role="presentation">i=0k1ci(ci1)2 要注意的是,模数为0的 a[0]要加一,因为这a[0] 个数本身就是满足条件的。 ( (x+1)x2x(x1)2" role="presentation">(x+1)x2x(x1)2==x )
代码: #include #include #include #define LL long long using namespace std; const int maxn=1e5+10; int a[maxn]; int main() { int n,k,x; LL sum; while(scanf("%d%d",&n,&k)!=EOF) { sum=0; memset(a,0,sizeof(a)); for(int i=1;i<=n;++i) { scanf("%d",&x); sum=(sum+x)%k; a[sum]++; } if(a[0]) a[0]++; // x*(x+1)/2-(x-1)*x/2==x %k==0本身就是k的倍数 LL ans=0; for(int i=0;iif(!a[i]) continue; ans=ans+(a[i]*1ll*(a[i]-1)/2); } printf("%lld ",ans); } return 0; }