Cod sursa(job #338343)

Utilizator ilincaSorescu Ilinca ilinca Data 5 august 2009 15:56:00
Problema Reguli Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <stdio.h> 

#define nmax 500005

int n, pi [nmax];
long long a [nmax];


void scan ()
{
	int i;
       	long long x, aux;
	scanf ("%d%lld", &n, &aux);
	for (i=1; i < n; ++i)
	{
		scanf ("%lld", &x);
		a [i]=x-aux;
		aux=x;
	}
}

int rez ()
{
	int i, q=0, u;
	pi [1]=0;
	for (i=2; i < n; ++i)
	{
		while (q && a [q+1] != a [i])
		       q=pi [q];
		if (a [q+1] == a [i]) 
			++q;
		pi [i]=q;
		//fprintf(stderr, "i=%d q=%d\n",i, q ); 
	}	

	for (i=2; i < n; ++i)
	{
		u=n-n%i; //perioada i; u=ultimul element din ultima perioada completa
		if ((pi [u]) && (u%pi [u] == 0) && (u/pi [u] == n/i)) 
			return i;
	}	

	return 1;
}

void print (int x)
{
	int i;
	printf ("%d\n", x);
	for (i=1; i <= x; ++i) 
		printf ("%lld\n", a [i]);
}

int main ()
{
	freopen ("reguli.in", "r", stdin);
	freopen ("reguli.out", "w", stdout);
	scan ();
	print (rez ());
	return 0;
}