Cod sursa(job #157710)

Utilizator razvi9Jurca Razvan razvi9 Data 13 martie 2008 11:05:20
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.66 kb
#include<cstdio>
const int size=600001;
int a[size],n,pi[size],x,y,i,k,j,c;
int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf("%d %d",&n,&y);
	n--;
	for(i=1;i<=n;i++){
		x=y;
		scanf("%d",&y);
		a[i]=y-x;}
	k=0;
	pi[1]=0;
	for(i=2;i<=n;i++){
		while(k>0&&a[k+1]!=a[i])
			k=pi[k];
		if(a[k+1]==a[i])
			++k;
		pi[i]=k;}
	for(i=1;i<n;i++){
		j=n%i;
		c=n/i;
		if(pi[n-j]>0 && (n-j)%(n-j-pi[n-j])==0 && c==(double)(n-j)/(n-j-pi[n-j])){
			for(k=n-j+1;k<=n;k++)
				if(a[k]!=a[k-n+j]) break;
			if(k>n) break;}}
	printf("%d\n",i);
	for(k=1;k<=i;k++)
		printf("%d\n",a[k]);
	fclose(stdout);
	return 0;
}