Cod sursa(job #373877)

Utilizator socheoSorodoc Ionut socheo Data 15 decembrie 2009 12:45:53
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include<stdio.h>
long long a[500001],km[500001],n,i,j,x0,x1,max;
void prefix()
{ km[1]=0;
  int k=0;
  for(int q=2;q<=n;q++)
  { while(a[q]!=a[k+1]&&k>0)
	  k=km[q];
   if(a[q]==a[k+1])
	   k++;
    km[q]=k;
	if(km[q]>=km[q-1]&&km[q-1]!=0)
		max=q;
  }
}
int perioada()
{  for(i=1;i<n;i++)
	{ long long r=n%i;
      long long c=n/i;
	  if(km[n-r]>0&&(n-r)%(n-r-km[n-r])==0&&(n-r)/(n-r-km[n-r])==c&&km[n]==km[r])
		  return i;
	}
return n;
	
}
int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf("%lld",&n);
	scanf("%lld",&x0);
	for(i=1;i<n;i++)
	{ scanf("%lld",&x1);
	  a[i]=x1-x0;
	  x0=x1;
	}

prefix();
int nr=perioada();
printf("%lld\n",nr);
for(i=1;i<=nr;i++)
	printf("%lld\n",a[i]);
	return 0;
}