历届试题 k倍区间

Myth丶恋晨 2023-07-11 13:59 38阅读 0赞

# 试题 历届试题 k倍区间 #

--------------------

资源限制
    时间限制：2.0s   内存限制：256.0MB

## 问题描述 ##

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

你能求出数列中总共有多少个K倍区间吗？  
输入格式  
　　第一行包含两个整数N和K。(1 <= N, K <= 100000)  
　　以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)  
输出格式  
　　输出一个整数，代表K倍区间的数目。

## 样例输入 ##

5 2
    1
    2
    3
    4
    5

## 样例输出 ##

## 数据规模和约定 ##

峰值内存消耗（含虚拟机） < 256M  
　　CPU消耗 < 2000ms

## 思路： ##

区间枚举？数据太大！  
预处理很容易想到前缀和。  
对于\[l,r\]，区间和能够整除k的条件是：  
（sum\[r\] - sum\[l-1\] ）% k= 0  
不再瞎推一下还是很难找到突破口！  
sum\[r\]%k = sum\[l-1\]%k

可以看出要满足前缀和取模相等，那么：  
设区间左边l 取值为i, **以r作为右区间**能够整除k的区间个数 等于 \*\*sum\[i\]%k&& i < r 的值 与 sum\[r\]%k 的值 相同 \*\* 的个数，这个 个数我们用一个cnt\[\]来存。  
比如： cnt\[sum\[i\]\]:表示到 i 时，前缀和%k = sum\[i\] 的个数。

### 注意：![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70] ###

所以结果**最后需要加上cnt\[0\]**

## 代码 ##

now code:  
同余定理：  
a - b = n\*k  
a和b除k，余数相等；  
此时只需要看之前有几个位置和当前位置同余即可；

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int N = 1e5+5;
    typedef long long LL;
    LL sum[N];
    LL cnt[N];
    int main()
    {
        
        int n,k;
        scanf("%d%d",&n,&k);
        int x;
        LL ans = 0;
        for(int i = 1; i <= n; i++)
        {
        
            scanf("%d",&x);
            x %= k;
            sum[i] = (sum[i-1] + x) % k;
        }
    		for(int i = 1; i <= n; ++i)
    		{
        
    			cnt[sum[i-1]]++;
    			ans += cnt[sum[i]];
    		}
        printf("%lld\n",ans);
        return 0;
    }

之前代码：

#include <iostream>
    #include <cstdio>
    using namespace std;
    const int N = 1e5+5;
    typedef long long LL;
    LL sum[N];
    LL cnt[N];
    int main()
    {
        
        int n,k;
        scanf("%d%d",&n,&k);
        int x;
        LL ans = 0;
        for(int i = 1; i <= n; i++)
        {
        
            scanf("%d",&x);
            x %= k;
            sum[i] = (sum[i-1] + x) % k;
            ans += cnt[sum[i]]++;
        }
        printf("%lld\n",ans+cnt[0]);
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200312140557540.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RiX3lvdXRo,size_16,color_FFFFFF,t_70