Cod sursa(job #416265)

Utilizator funkydvdIancu David Traian funkydvd Data 12 martie 2010 13:53:21
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
#include<cstring>
using namespace std;
long long s[500001],x,y,pi[500001];
int n;
bool ok[500001];
void prefix ()
{
	int 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 ("%d", &n);
	scanf ("%lld", &x);
	n--;
	for (int i=1; i<=n; i++)
	{
		scanf ("%lld", &y);
		s[i]=y-x;
		x=y;
	}
	prefix();
	int f=0,i=1;
	long long r,c;
	while (f==0 && i<=n)
	{
		r=n%i,c=n/i;
		if (ok[r]==1) if(pi[n-r]>0) if( (n-r)%(n-r-pi[n-r])==0) if ((n-r)/(n-r-pi[n-r])==c)  f=1;
		i++;
	}
	i--;
	printf ("%d\n", i);
	for (f=1; f<=i; f++) printf ("%lld\n", s[f]);
return 0;
}