k倍区间

题目 K倍区间

思路分析

考试时应该是想不到优化的

拿一半分

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long ll;
const int N=100010;
int s[N],a[N],res[N];
int n,k;

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k;

    /*
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }

    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){
            if((s[j]-s[i-1])%k==0){
                cnt++;
            }
        }
    }
    cout<<cnt;
    */

    /*
    两重循环 tle
    考虑再把一层循环减掉
    (s[j]-s[i-1])%k 等价于 s[j]%k==s[i-1]%k
    如何理解?
    sum[j] % k 和 sum[i-1] % k 的余数如果相等
    那么sum[j] - sum[i-1]的差值必然是k的倍数
    比如13 % 7 和 20 % 7 (20-13)%7 =0;

    问题转变成了 累加该数之前与它模k余数相等的数有多少个
    res[sum[i]] 表是s[i]出现过的次数
    如 sum[i] = 3，在后边的循环中，又出现了一个 sum[i] = 3
    那么此时，这个“3”可以和前边出现过的所有的“3”分别构成一个K倍区间
    前边的“3”一共出现过res[sum[i]] 次，所以 此时又新增了res[sum[i]]个K倍区间

    最后还要考虑余数0本身就可以满足%k==0而不需要另外一个0与其组合 所以ans加上res[0] 得到答案ans
    */

    ll ans=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=(s[i-1]+a[i])%k;
        ans+=res[s[i]];
        res[s[i]]++;
    }
    cout<<ans+res[0]<<endl;

    return 0;
}

同类题型

视频讲解

⬅️ 环形链表2 🏠 00-刷题理模型 ➡️ 前缀和