Cod sursa(job #416249)

Utilizator funkydvdIancu David Traian funkydvd Data 12 martie 2010 13:38:39
Problema Reguli Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include<cstdio>
#include<cstring>
using namespace std;
long long s[500001],n,x,y,pi[500001];
bool ok[500001];
void prefix ()
{
	long long i , q = 0;
	for( i = 2; i <= n ; ++i ) 
	{
		while (q&&s[q + 1]!=s[i]) q=pi[q];
		if (s[q + 1]==s[i]) q++;
		pi[i] = q;
	}
	long long x=pi[n];
	while (x)
	{
		ok[x]=1;
		x=pi[x];
	}
}
int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	scanf ("%lld", &n);
	scanf ("%lld", &x);
	n--;
	for (int i=1; i<=n; i++)
	{
		scanf ("%lld", &y);
		s[i]=y-x;
		x=y;
	}
	prefix();
	long long f=0,i=1,r,c;
	while (f==0)
	{
		r=n%i,c=n/i;
		if (pi[n-r]>0&&( (n-r)%(n-r-pi[n-r])==0) && ((n-r)/(n-r-pi[n-r])==c) && ok[r]==1) f=1;
		i++;
	}
	i--;
	printf ("%lld\n", i);
	for (f=1; f<=i; f++) printf ("%lld\n", s[f]);
return 0;
}