K倍区间（蓝桥杯每日一题）

ゞ浴缸里的玫瑰 2024-03-26 12:48 24阅读 0赞

## K倍区间（蓝桥杯每日一题） ##

给定一个长度为 N的数列，A1,A2,…AN，如果其中一段连续的子序列 Ai,Ai+1,…Aj之和是 K的倍数，我们就称这个区间 \[i,j\]是 K倍区间。

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

输入格式  
第一行包含两个整数 N和 K。

以下 N行每行包含一个整数 Ai。

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

数据范围  
1≤N,K≤100000  
,  
1≤Ai≤100000

输入样例：  
5 2  
1  
2  
3  
4  
5  
输出样例：  
6

### 算法思路 ###

这个题算得上是前缀和的一个应用  
这里想要知道一个区间是否为k的倍数，需要对每一个前缀和区间进行计数  
这个理论就是对于一个区间\[l, r\],  
(sum\[i\]-sum\[j\])%k=0，那么有sum\[i\]%k-sum\[j\]%k=0，可以推导出  
sum\[r\] % k 和 sum\[l-1\] % k 的余数如果相等  
那么sum\[r\] - sum\[l-1\]的差值必然是k的倍数  
这样就可以理解ans += res\[sum\[i\]\]的含义了  
res\[sum\[i\]\]想要可以被ans+=需要满足后面的前缀和%k之后  
获得了同样的一个结果，因为每次的res\[sum\[i\]\]的结果都会++，统计  
不同的res\[sum\[i\]的出现次数，一旦后面这个结果触发了  
ans += res\[sum\[i\]\]这个条件，那么就代表出现了至少一个区间\[l,r\]  
使得满足题目的条件是k的倍数  
最后的结果还需要加上res\[0\],这里指的是某个数是k的倍数，ans存放的是至少有两个数的区间。

### C++ ###

#include<bits/stdc++.h>
    using namespace std;
    
    const int N = 1e5 + 10;
    typedef long long ll;
    int sum[N], a[N], res[N];
    int n, k;
    ll ans = 0;
    /*
    这个题算得上是前缀和的一个应用
    这里想要知道一个区间是否为k的倍数，需要对每一个前缀和区间进行计数 
    这个理论就是对于一个区间[l, r],
    (sum[i]-sum[j])%k=0，那么有sum[i]%k-sum[j]%k=0，可以推导出
    sum[r] % k 和 sum[l-1] % k 的余数如果相等
    那么sum[r] - sum[l-1]的差值必然是k的倍数 
    这样就可以理解ans += res[sum[i]]的含义了
    res[sum[i]]想要可以被ans+=需要满足后面的前缀和%k之后
    获得了同样的一个结果，因为每次的res[sum[i]]的结果都会++，统计
    不同的res[sum[i]的出现次数，一旦后面这个结果触发了
    ans += res[sum[i]]这个条件，那么就代表出现了至少一个区间[l,r]
    使得满足题目的条件是k的倍数 
    最后的结果还需要加上res[0],这里指的是某个数是k的倍数，ans存放的是至少有两个数的区间。
    */
    int main()
    {
        
        cin >> n >> k;
        for (int i = 1; i <= n; ++ i)
        {
        
            cin >> a[i];
            sum[i] = (sum[i - 1] + a[i]) % k;
            // cout << "sum[i]:" << sum[i] << endl;
            ans += res[sum[i]];
            res[sum[i]] ++;
        }
        cout << ans + res[0] << endl;
        return 0;
    }

### Java ###

import java.util.\*;

public class Main  
\{  
static int N = 100010;  
static int \[\] sum = new int \[N\];  
static int \[\] a = new int \[N\];  
static int \[\] res = new int \[N\];  
public static void main(String\[\] args)  
\{  
Scanner in = new Scanner(System.in);  
int n, k, ans = 0;  
n = in.nextInt();  
k = in.nextInt();  
for (int i = 1; i <= n; ++ i)  
\{  
a\[i\] = in.nextInt();  
sum\[i\] = (sum\[i - 1\] + a\[i\]) % k;  
ans += res\[sum\[i\]\];  
res\[sum\[i\]\] ++;  
\}  
System.out.println(ans + res\[0\]);  
\}  
\}