Powered by:NEFU AB_IN

小宝的幸运数组

题意：有一个长度为$n$的数组，求最长的子数组，条件为它的和能被$k$整除。

知识点：贪心 + 前缀和

思路：用前缀和预处理数组，得数组$b$，那么第$i$位到第$j$位的子串和为$b[j]-b[i-1]$。重点在于：
$$(b[j]-b[i-1])\%k=b[j]\%k-b[i-1]\%k$$
之后只需要贪心的寻找距离最远的有着相同取模结果的两端即可。

/*
 * @Description: 
 * @Author: NEFU AB_IN
 * @version: 1.0
 * @Date: 2021-02-16 17:07:15
 * @LastEditors: NEFU AB_IN
 * @LastEditTime: 2021-03-07 19:51:36
 */
#include<bits/stdc++.h>
using namespace std;
#define ll                          long long
#define ull                         unsigned long long
#define ld                          long double
#define db                          double
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define MP                          make_pair
#define PB                          emplace_back
#define SZ(X)                       ((int)(X).size())   
#define mset(s, _)                  memset(s, _, sizeof(s))
#define IOS                         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl                        "\n"
#define forn(i, l, r)                for (int i = l; i <= r; i++)
typedef pair<int, int>               pii;
typedef pair<ll, ll>                 pll;
const int INF = 0x3f3f3f3f;

const int N = 1E5 + 10;
int a[N], b[N], f[N];

void solve(){
    int n, k, ans = -1;
    cin >> n >> k;
    mset(f, -1);
    forn(i, 1, n) cin >> a[i], b[i] = (b[i - 1] + a[i]) % k;
    forn(i, 0, n){
        if(f[b[i]] != -1){
            ans = max(ans, i - f[b[i]]); 
        }
        else{
            f[b[i]] = i; // 存这次和为b[i]的下标
        }
    }
    cout << ans << endl;
}

int main()
{
    IOS;
    int t;
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

完结。