Doces de Dia das Bruxas

doces.cpp

#include <cstdio>
#include <cstring>

#define MAXN 100100

int c, n, s[MAXN], resto[MAXN];

int main(){
	
	// para cada caso
	while(scanf("%d %d", &c, &n)and n and c){
		
		// defino todos os valores de resto para -1, ou seja, não encontrados
		memset(resto, -1, sizeof resto);
		
		// caso especial de n=c, e todos os s_i serem distintos
		resto[0]=0;
		
		// leio a entrada e salvo em s
		for(int i=1; i<=n; i++) scanf("%d", &s[i]);
		
		// para cada vizinho
		for(int i=1; i<=n; i++){
			
			// descubro o valor real de seu s, acumulando o s anterior
			s[i]+=s[i-1];
			
			// e guardando módulo c
			s[i]%=c;
			
			// se esse resto já foi encontrado no vetor, na posição k
			if(resto[s[i]]>=0){
				
				// imprimo os índices de k+1 a i
				// com o cuidado de não imprimir um espaço a mais no final
				printf("%d", resto[s[i]]+1);		
				for(int j=resto[s[i]]+2; j<=i; j++) printf(" %d", j);	
				printf("\n");
				
				// e paro de percorrer o vetor
				break;
			}
			
			// caso contrário, guardo o novo resto encontrado
			resto[s[i]]=i;
		}
	}
	
	return 0;
}