[蓝桥杯 2017 省 B] k 倍区间
题目描述
给定一个长度为 NNN 的数列,A1,A2,⋯ANA_1,A_2, \cdots A_NA1,A2,⋯AN,如果其中一段连续的子序列 Ai,Ai+1,⋯Aj(i≤j)A_i,A_{i+1}, \cdots A_j(i \le j)Ai,Ai+1,⋯Aj(i≤j) 之和是 KKK 的倍数,我们就称这个区间 [i,j][i,j][i,j] 是 KKK 倍区间。
你能求出数列中总共有多少个 KKK 倍区间吗?
输入格式
第一行包含两个整数 NNN 和 KKK(1≤N,K≤105)(1 \le N,K \le 10^5)(1≤N,K≤105)。
以下 NNN 行每行包含一个整数 AiA_iAi(1≤Ai≤105)(1 \le A_i \le 10^5)(1≤Ai≤105)。
输出格式
输出一个整数,代表 KKK 倍区间的数目。
样例 #1
样例输入 #1
5 2
1
2
3
4
5
样例输出 #1
6
提示
时限 2 秒, 256M。蓝桥杯 2017 年第八届
分析
题目很简单,我的第一反应就是暴力,直接双重循环枚举左右区间
import java.util.*;
public class Main{static int res;public static void main(String[] args){Scanner scan = new Scanner(System.in);int n = scan.nextInt();int k = scan.nextInt();int[] a = new int[n+1];for(int i = 0;i<n;i++){a[i]=scan.nextInt();}for(int i = 0;i<n;i++){int q = 0;for(int j=i;j<n;j++){q+=a[j];if(q%k==0) res++;}}System.out.println(res);}
}
代码没啥问题,但会超时,
我们考虑优化,区间和问题,自然想到的就是前缀和,借此可以优化一维,但是如果就仅仅优化这个还是不够的,依旧会超时,这我们就不得不思考一种新的方法来判断是否满足K倍区间,根据同余定理 ,因此有如下思路
已知a
那么我们就可以将前缀和模k的值为0,1,2…k-1的区间数分别求出来,然后分别计算。
import java.util.Scanner;public class Main {// 后面用不到原数列,所以只存储前缀和public static int[] sum = new int[100005];// 用来统计相同余数的的个数public static long[] remainder = new long[100005];public static void main(String[] args) {Scanner sc = new Scanner(System.in);long ans = 0;// 前0项和是0,注意余数为0开始就出现一次remainder[0] = 1;int n = sc.nextInt();int k = sc.nextInt();for (int i = 1; i <= n; i++) {int num = sc.nextInt();sum[i] = sum[i - 1] + num;remainder[sum[i] % k]++;}sc.close();for (int i = 0; i < k; i++)ans += (remainder[i] * (remainder[i] - 1)) >> 1;System.out.println(ans);}
}