Find a multiple 抽屉原理

传送门：https://vjudge.net/contest/374932#problem/A

题意

　　给你长为n的一个序列，要求在序列中找到连续的一些数，使他们的和是n的倍数，输出抽多少个，并分别输出他们。

思路

　　若用前缀和枚举子串，复杂度为n方，会t。

　　考虑每一个前缀和对n的模数设为x，若i=k的时候x=0那意味着1到i是一个符合的序列。

　　考虑n个前缀和的模数，模数都在1到n-1之间，所以必定有两个模数相同，设他们的下标为l和r，sum[l]%n==x且sum[r]%n==x，那sum[r]-sum[l]这部分和%n就等于0了，所以我们只要找到l和r输出l+1到r的序列就行。

AC代码

#include<iostream>
#include<string.h>
using namespace std;
typedef long long ll;
const int maxn=1e4+5;
ll a[maxn],sum[maxn],num[maxn];
int vis[maxn];
int n;
int main()
{
    while(cin>>n){
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum[i]=sum[i-1]+a[i];
            num[i]=sum[i]%n;
        }
        int l=1,r=0;
        for(int i=1;i<=n;i++){
            if(num[i]==0){
                l=1;r=i;
                break;
            }
            if(vis[num[i]]==0) vis[num[i]]=i;
            else{
                l=vis[num[i]]+1;r=i;
                break;
            }
        }
        cout<<r-l+1<<'
';
        for(int i=l;i<=r;i++)
            cout<<a[i]<<'
';
    }
    return 0;
}