P8649 [蓝桥杯 2017 省 B] k 倍区间

我被坑了题目描述给定一个长度为 N 的数列A 1 ,A 2 ,⋯A N​如果其中一段连续的子序列 A i ,A i1 ,⋯A j​(i≤j) 之和是 K 的倍数我们就称这个区间 [i,j] 是 K 倍区间。你能求出数列中总共有多少个 K 倍区间吗输入格式第一行包含两个整数 N 和 K (1≤N,K≤105)。以下 N 行每行包含一个整数 Ai​(1≤Ai​≤105)。输出格式输出一个整数代表 K 倍区间的数目。输入输出样例输入 #1复制5 212345输出 #1复制6说明/提示时限 2 秒, 256M。蓝桥杯 2017 年第八届这是一开始我的代码#includebits/stdc.husingnamespacestd;inta[1000001];intmain(){longlongs0,ans0;intn,k;cinnk;for(inti1;in;i){cina[i];a[i]a[i-1];}for(inti1;in;i){for(intji;jn;j){if((a[j]-a[i-1])%k0)ans;}}coutans;}当时本人哈哈哈又要对一题了此时的锣鼓有问题超超超超超超超超----超空间欲哭无泪中大家可不要像我一样喜提TLE正确解法#includebits/stdc.husingnamespacestd;intmain(){s ios::sync_with_stdio(0);//加快输入输出的简称优化cin.tie(0),cout.tie(0);intn,a[100001]{0},k,ans0,sum0;cinnk;a[0]1;for(inti0;in;i){intx;cinx;sumx;a[sum%k];sum%k;}for(inti0;ik;i)ans(a[i]*(a[i]-1))1;coutans;return0;}本题坑点要开 long long。无了OK,到此为止下课