poj3370——Halloween treats

44424742

抽屉原理.同时 sum[]有dp的味道！
详见:http://www.cppblog.com/pcfeng502/archive/2009/10/18/98902.aspx
http://www.cnblogs.com/woodfish1988/archive/2007/09/25/905784.html
第二个博客给出证明！太强大了！
#include<iostream>#include<cstdio>#include<cstring>using namespace std;#define maxn 100005int num[maxn],vis[maxn],sum[maxn];int main(){int n,c,i;while(cin>>c>>n&&n&&c){int mod=0,k;memset(vis,false,sizeof(vis));vis[mod]=true;bool flag=true;int position;for(i=1;i<=n;i++){scanf("%d",&num[i]);if(flag){mod=(mod+num[i]%c)%c;if(vis[mod]){ position=i;flag=false;k=mod;}else {vis[mod]=true; sum[i]=mod;}}   }for(i=position-1;i>=0;i--){if(sum[i]==k) break;}for(k=i+1;k<=position;k++)printf("%d ",k);printf("\n");}return 0;}