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

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

原题链接：点击查看

数据范围：

• \(1 \le N,K \le 10^5\)
  
• \(1 \le A_i \le 10^5\)
  

解题思路

前缀和 + 模运算

• 区间 \([i,j]\) 的和 = \(pre[j] - pre[i-1]\)
  
• 若该区间和是k的倍数，则满足 \((pre[j] - pre[i-1]) \bmod k = 0\)，即 \(pre[j] \bmod k = pre[i-1] \bmod k\)
  
• 用数组统计每个余数出现的次数，遍历过程中累加对应余数的计数，即可得到总区间数
  
• 初始化余数0的计数为1，处理前缀和本身就是k倍数的情况
  

复杂度分析

• 时间复杂度：\(O(N)\)，仅遍历一次数组，常数级操作
  
• 空间复杂度：\(O(K)\)，开辟长度为k的计数数组
  

代码实现

[code]    int n,k,x;    LL ans=0;    cin>>n>>k;    vectorcnt(k,0);    cnt[0]=1;    LL pre=0;    rep(i,0,n){        cin>>x;        pre=(pre+x)%k;        // 累加当前余数已出现的次数        ans+=cnt[pre];        cnt[pre]++;    }    cout