【蓝桥杯】K倍区间

本是古典何须时尚 2024-03-24 10:07 32阅读 0赞

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

### 题目描述 ###

给定一个长度为  N N N 的数列， A 1 , A 2 , ⋯ A N A\_1,A\_2, \\cdots A\_N A1,A2,⋯AN，如果其中一段连续的子序列  A i , A i + 1 , ⋯ A j ( i ≤ j ) A\_i,A\_\{i+1\}, \\cdots A\_j(i \\le j) Ai,Ai\+1,⋯Aj(i≤j) 之和是  K K K 的倍数，我们就称这个区间  \[ i , j \] \[i,j\] \[i,j\] 是  K K K 倍区间。

你能求出数列中总共有多少个  K K K 倍区间吗？

### 输入格式 ###

第一行包含两个整数  N N N 和  K K K ( 1 ≤ N , K ≤ 1 0 5 ) (1 \\le N,K \\le 10^5) (1≤N,K≤105)。

以下  N N N 行每行包含一个整数  A i A\_i Ai ( 1 ≤ A i ≤ 1 0 5 ) (1 \\le A\_i \\le 10^5) (1≤Ai≤105)。

### 输出格式 ###

输出一个整数，代表  K K K 倍区间的数目。

### 样例 \#1 ###

#### 样例输入 \#1 ####

5 2
    1  
    2  
    3  
    4  
    5

#### 样例输出 \#1 ####

### 提示 ###

时限 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);
        }
    }

代码没啥问题，但会超时，

![在这里插入图片描述][444a89501ab44a229e26b0d1b7641c65.png]

我们考虑优化，区间和问题，自然想到的就是前缀和，借此可以优化一维，但是如果就仅仅优化这个还是不够的，依旧会超时，这我们就不得不思考一种新的方法来判断是否满足K倍区间，根据**同余定理** ，因此有如下思路

已知a<b，suma，sumb分别为a，b的前缀和（从序列第一个数到它自身的所有数之和），且suma%k=x，sumb%k=x。那么可得（sumb-suma）%k=0。即由b-a产生的区间c，一定为一个k倍区间

那么我们就可以将前缀和模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);
        }
    }

![在这里插入图片描述][1bc2bf27babd4e808e12f7efebe79d32.png]

[444a89501ab44a229e26b0d1b7641c65.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/0124f6a0e3714f01b948806dbeb2feac.png
[1bc2bf27babd4e808e12f7efebe79d32.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2162ff5812e04e5496d02b52f7e21eb3.png