Posted on 2008-07-30 00:41
Hero 閱讀(135)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
/*
ID: wangzha4
LANG: C++
TASK: PKU3370
*/
//根據抽屜原理一定有解
//remain[i]記錄前i項和對inc的模
//if( 存在remain[i]==0 ) -- 直接輸出1～i
//else remain[i]的取值是[1~n-1]
//而remain[i]共有n個值 -- 由抽屜原理 -- 定存在i，j滿足remain[i]==remain[j]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define llong unsigned long long
#define unint unsigned int
#define printcrlf printf( "\n" )
const int inf = 1000000 ;
const int size = 100010 ;
int inc, inn ;
int data[size] ;
int remain[size] ;
int flag[size] ;
int main()
{
#ifndef ONLINE_JUDGE
freopen( "in.txt", "r", stdin ) ;
freopen( "out.txt","w",stdout ) ;
#endif
while( scanf( "%d %d",&inc,&inn ) != EOF && ( inc||inn ) )
{
memset( flag, 0, sizeof(flag) ) ;
remain[0] = 0 ;
for( int i=1; i<=inn; i++ ){
scanf( "%d",&data[i] ) ;
remain[i] = (remain[i-1]+data[i]) % inc ;
}
for( int i=1; i<=inn; i++ ){
if( 0 == remain[i] ){
for( int j=1; j<i; j++ ) printf( "%d ",j ) ;
printf( "%d\n",i ) ;
break ;
}
else{
if( flag[remain[i]] ){
for( int j=flag[remain[i]]+1; j<i; j++ ) printf( "%d ",j ) ;
printf( "%d\n",i ) ;
break ;
}
else{
flag[remain[i]] = i ;
}
}
}
}//while
return 0 ;
}