Cod sursa(job #458716)

Utilizator irene_mFMI Irina Iancu irene_m Data 25 mai 2010 21:53:31
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>
#define infile "reguli.in"
#define outfile "reguli.out"
#define MaxN 500024

long long n,d[MaxN],pi[MaxN],ok[MaxN],L,max,x;

void cit()
{
	long long i,a,b;
	freopen(infile,"r",stdin);
	scanf("%lld%lld",&n,&a);
	for(i=1;i<n;i++)
	{
		scanf("%lld",&b);
		d[i]=b-a;
		a=b;
	}
}

void prefix()
{
	long long k=0,i;
	for(i=2;i<n;i++)
	{
		while(k && d[k+1]!=d[i])
			k=pi[k];
		if(d[k+1]==d[i])
			k++;
		pi[i]=k;
		if(k && i%(i-k)==0)
			max=k;
	}
}

void OK()
{
	long long k;
	n--;
	k=pi[n];
	while(!ok[k])
	{
		ok[k]=1;
		k=pi[k];
	}
}

void perioada()
{
	long long i,r,c;
	L=n;
	ok[0]=1;
	for(i=n-1;i>=1;i--)
	{
		r=n%i;
		c=n/i;
		if(pi[n-r] && (((n-r)%(n-r-pi[n-r])==0 && (n-r)/(n-r-pi[n-r])==c) || c==1 || (i%(i-pi[i])==0) && pi[i]) && ok[r])
			L=i;
	}
}

void afis()
{
	long long i;
	freopen(outfile,"w",stdout);
	printf("%lld\n",L);
	for(i=1;i<=L;i++)
            printf("%lld\n",d[i]);
}

int main()
{
	cit();
	prefix();
	OK();
	perioada();
	afis();
	return 0;
}