ZZULIOJ1531-小L的区间求和(是K的倍数的最长区间和)

发布于 2019-08-14  528 次阅读


问题传送门:

题意:

找到一个连续的区间,这个区间的和能够被k整除,
满足条件的最长的区间长度是多少

分析:

首先需要知道一件事,如果两个数a ,b 对 k 取模的余数是一样的
那么 a-b 一定是 k 的倍数。
基于此,我们可以维护一个给出数组的前缀和
遍历前缀和数组,依次对 k 取模,
如果余数m是 0 ,直接更新 ans,此时的长度一定是目前最长的
如果余数m不是 0, 就记录一下出现这个余数的坐标,
如果这个余数m之前已经被记录过,就 i-pos[m] ,
这个区间的和一定是 k 的倍数。
#include <iostream>

using namespace std;

typedef long long LL;
const int MAXN = 1e5+10;

int a[MAXN];
LL sum[MAXN];

int pos[100];

int main()
{
    int n, k, m, ans = 0;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        sum[i] = a[i] + sum[i-1];
    }
    for (int i = 1; i <= n; i++)
    {
        m = sum[i] % k;
        if (m == 0)
            ans == m;
        else
        {
            if (pos[m]==0)
                pos[m] = i;
            ans = max(ans, i-pos[m]);
        }
    }

    cout << ans << endl;
    return 0;
}

Simple And Clear