摘要：
描述给定一个数字，需要从中选择几个数字，使其总和为的倍数。很容易证明你能找到它。解决方案如果数字是的倍数，将直接输出。否则，考虑查找前缀和序列并，并将其设置为（s[]），则必须有两个相同的前缀和序列，并将它设置为，则间隔必须满足问题的含义。
Description
给定 (n) 个数，要求从其中选出若干个数使得其和是 (n) 的倍数。容易证明一定能找到。
Solution
如果有一个数是 (n) 的倍数则直接输出，否则，考虑求出前缀和序列并 (mod n)，设为 (s[])，则 (s[0],s[1],...,s[n]) 中一定有两个相同的（鸽巢原理），设为 (s[l],s[r])，则 ([l+1,r]) 区间一定满足题意。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000505;
int n,a[N],s[N];
signed main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
for(int i=0;i<=n;i++) s[i]=s[i]%n;
int flag=0;
for(int i=1;i<=n;i++) if(a[i]%n==0) flag=i;
if(flag)
{
cout<<flag<<" "<<a[flag]<<endl;
}
else
{
map<int,int> mp;
int a1=0,a2=0;
for(int i=0;i<=n;i++)
{
if(mp[s[i]])
{
a1=mp[s[i]];
a2=i;
break;
}
else
{
mp[s[i]]=i;
}
}
for(int i=a1+1;i<=a2;i++)
{
cout<<i<<" "<<a[i]<<endl;
}
}
system("pause");
}