基础算法——前缀和和同余定理——K倍区间

本文主要是介绍基础算法——前缀和和同余定理——K倍区间，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题源：P8649 [蓝桥杯 2017 省 B] k 倍区间 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

一、预备知识（自行学习）

1、一维前缀和

2、同余定理

---

二、解题代码

• f[x] --- 某个前缀和对k取余的结果是x的个数
• f[0]=1---取余是0那这个区间就是一个K倍区间，而其他的需要两个区间的差才能构成K倍区间
• 先求res再求f[sum]的原因也是其他的需要两个区间的差才能构成K倍区间

package 前缀和;
import java.util.*;
public class LGP8649 {public static void main(String []args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int k = in.nextInt();int a[] = new int[n];int f[] = new int[k];f[0] = 1;long res = 0;int sum = 0;for(int i=0;i<n;i++)a[i] = in.nextInt();for(int i=0;i<n;i++) {sum+=a[i];sum%=k;res+=f[sum];f[sum]++;}System.out.print(res);}
}

这篇关于基础算法——前缀和和同余定理——K倍区间的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---