Cod sursa(job #496730)

Utilizator cosmin79Carabet Cosmin Andrei cosmin79 Data 30 octombrie 2010 13:50:48
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
#include <stdio.h>
#define NMAX 500005
#define ll long long
int n,r,pi[NMAX],rez;
ll A[NMAX],B[NMAX];
char marc[NMAX];
void read()
{
	scanf("%d",&n);
	int i;
	for (i=1; i<=n; i++)
		scanf("%lld",&A[i]);
	for (i=2; i<=n; i++)
		B[++r]=A[i]-A[i-1];
}
void prefix()
{
	int i,q=0;
	for (i=2; i<=r; i++)
	{
		while (B[q+1]!=B[i] && q>0)
			q=pi[q];
		if (B[q+1]==B[i]) q++;
		pi[i]=q;
	}
}
void precompute()
{
	int i,q=pi[r];
	marc[0]=1;
	while (q)
	{
		marc[q]=1;
		q=pi[q];
	}
}
int solve()
{
	int i,p,q,s;
	prefix();
	precompute();
	for (i=1; i<=r; i++)
	{
		p=r/i; q=r%i; s=p*i;
		if (s%(s-pi[s])==0 && pi[s]>0 && pi[s]==s-i && marc[q])
			return i;
	}
	return r;
}
int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);
	read();
	rez=solve();
	printf("%d\n",rez);
	for (int i=1; i<=rez; i++)
		printf("%lld\n",B[i]);
	return 0;
}