题目描述

给定包含 n 个整数的数列，从中选取一段连续子数列，使其元素之和能被 k 整除。

请找出符合要求的最长连续子数列并输出其长度以及子数列本身；如果符合要求的最长连续子数列有多个，则输出起始位置最靠后的那个子数列。如果不存在符合要求的子数列，则输出 −1。

例如：当 n=7，k=7，数列为 7、3、4、1、5、14、9 时：

• 连续子数列 {7}、{7,3,4}、{3,4} 和 {5,14,9} 的和都能被 7 整除；
• 其中最长的连续子数列有 {7,3,4} 和 {5,14,9}，起始位置最靠后的是 {5,14,9}；
• 故符合要求的最长连续子数列长度为 3，子数列为 5 14 9。

输入格式

• 第一行输入两个整数 n 和 k（1≤n≤105，2≤k≤108），整数之间以一个空格隔开；
• 第二行输入 n 个整数（1≤ 整数 ≤104），整数之间以一个空格隔开。

输出格式

如果存在符合要求的最长连续子数列，则输出为两行：

1. 第一行输出一个整数，表示最长连续子数列的长度；
2. 第二行输出若干个整数，表示起始位置最靠后的最长连续子数列，整数之间以一个空格隔开。

如果不存在符合要求的子数列，则输出 −1。

输入输出样例

输入 #1复制

7 7
7 3 4 1 5 14 9

输出 #1复制

3
5 14 9

同余定理，若a%k==m,b%k==m,(b-a)%k==0 算出前i项和对k取模的值然后存在一个新数组里

    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        b[i]=sum[i]%k;
    }

问题就变成了求一个非负整数数组中两个相等的数之间间隔最大，每次找到的时候顺便记录下两个数的下标，方便后续输出最长的子序列 对于求解后面这个问题怎么做呢? 如果b[i]=0就先不判断，b[i]=0代表着前i项和是k的倍数 我们可以存储每个数最后一次的位置

map<int,int> m;
for(int i=1;i<=n;i++){
        if(b[i]!=0){
            m[b[i]]=i;
        }
    }

然后遍历一遍数组，判断当前数出现的位置与当前数最后一次出现的位置之差 如果变大了就存储下来并且更新左右下标 题目要求输出位置靠后的最长子序列 我们只需要在相等的时候也更新就可以保证了

for(int i=1;i<=n;i++){
        if(m[b[i]]-i>=ans&&b[i]!=0){
            l=i,r=m[b[i]];
            ans=m[b[i]]-i;
        }
    }

最后在与所有b[i]=0比较一遍取一个最大的值出来就可以啦

for(int i=1;i<=n;i++){
        if(b[i]==0&&i>ans){
            l=0;r=i;
            ans=i;
        }
    }

如果ans=0说明不存在符合要求的子序列 最后按我们记录的左右下标l,r依次输出原数组中的值即可 ac代码

#include<bits/stdc++.h>
using namespace std;
int n,k,l,r,ans;
int a[100005],sum[100005],b[100005];
map<int,int> m;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        b[i]=sum[i]%k;
    }
    for(int i=1;i<=n;i++){
        if(b[i]!=0){
            m[b[i]]=i;
        }
    }
    for(int i=1;i<=n;i++){
        if(m[b[i]]-i>=ans&&b[i]!=0){
            l=i,r=m[b[i]];
            ans=m[b[i]]-i;
        }
    }
    for(int i=1;i<=n;i++){
        if(b[i]==0&&i>ans){
            l=0;r=i;
            ans=i;
        }
    }
    if(ans==0){
        cout<<-1;
        return 0;
    }
    cout<<ans<<endl;
    for(int i=l+1;i<=r;i++){
        cout<<a[i]<<" ";
    }
}

我比较笨，但这是我自己想出来的，望大家支持！！！