选数(Daimayuan 456)

传送门

题目大意

给你\(n\)个数，要求选出若干个数使得相加之和\(\mod n==0\)，输出选择的数的个数以及下标，不存在则输出\(-1\)\((1\leq n\leq10^5,1\leq a_i\leq10^9)\)

思路

我们可以先处理出对\(n\)取模后的前缀和，然后可以发现，\(sum[0\rarr n]\)最多只有\(n\)个数，而又有\(n+1\)个位置，于是可以推断出一定至少有两个位置上的数相同，于是问题就解决了。

代码

#include
using namespace std;
int a[100005],b[100005];
int main()
{
    int n;
    scanf("%d",&n);
    b[0]=-1;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        a[i]%=n;
        a[i]=(a[i]+a[i-1])%n;
        b[i]=-1;
    }
    for(int i=0;i<=n;i++)
    {
        if(b[a[i]]==-1)b[a[i]]=i;
        else
        {
            printf("%d\n",i-b[a[i]]);
            for(int j=b[a[i]]+1;j<=i;j++)printf("%d ",j);
            return 0;
        }
    }
    return 0;
}