P8649[蓝桥杯2017省B]k倍区间--前缀和--同余定理【蓝桥杯简单题-必开longlong】

P8649 [蓝桥杯 2017 省 B] k 倍区间--前缀和--同余定理 题目 分析代码 还有一件事【老爹音】

题目

分析

首先，看到”连续子序列求和”这一要求时，我们果断选择前缀和解答。

接着就要用到一个非常巧妙的“同余定理”——如果 sum[j] % K == sum[i] % K，这意味着 sum[j] - sum[i] 是 K 的倍数

（其实不难理解，就是2个都有多的一步分，将2个相减，刚好让其差%k=0，满足题目条件0）

其中运用最巧妙的是ans += y[sum[i] % k]++;【注意++的运算优先级，这个++是为下一次r准备的 太牛逼了！】 运用哈希表的方法存储余数出现的次数， 例如：出现第一个余数3时，ans+=0，y[3]=1; 出现第二个余数3时，ans+=1，y[3]=2；【y的每一次自加都是为下一次做准备】 出现第三个余数3时，ans+=2，y[3]=3； （出现n个数的余数相等时，他们的区间个数为n-1个）

sum[]数组明明是从1开始存储的，为什么循环要从0开始？ 因为题中说到区间[i,j]（i<=j），所以若数值本身是k的倍数也应被统计 例：k=3,数组[3,0,3]，但若从1开始，第一个3是不会被计入的 模拟： i=0 ans+=0；y[0]=1； i=1 ans+=1；y[1]=2； i=2 ans+=2；y[2]=3； i=3 ans+=3；y[3]=4；

综上可知，若i从1开始遍历，会少加一个自身能被K整除的情况 代码 #include <iostream> #include <vector> #include <string> #include <algorithm> #include <math.h> #include <queue> #include <cctype> using namespace std; long long ans; int n, k; long long sum[100010], y[100010]; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> sum[i]; sum[i] += sum[i - 1]; } for (int i = 0; i <= n; i++) { ans += y[sum[i] % k]++; } cout << ans << endl; return 0; } 还有一件事【老爹音】

这种代码比较少的题目，【说简单吧，有点难想到】，蓝桥杯这个老Y逼啊，测试的数据都得开到long long 才能通过【不开long long 见祖宗】