Cod sursa(job #24692)

Utilizator ionescu_bogdanIonescu Bogdan-Gabriel ionescu_bogdan Data 3 martie 2007 12:50:46
Problema Reguli Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define nmax 500010

long long n,a[nmax],i,j,sol,pi[nmax],r,c;

void pref()
{
	long long k=0;
	pi[1]=0;
	for (int q=2;q<=n;q++)
	{
		while ((k>0)&&(a[k+1]!=a[q]))
			k=pi[k];
		if (a[k+1]==a[q])
			++k;
		pi[q]=k;
	}
}

inline int ok(int l)
{
	r=n%l,c=n/l;
	if (pi[n-r]==0)
		return 0;
	if ((n-r)%(n-r-pi[n-r])!=0)
		return 0;
	if ((n-r)/(n-r-pi[n-r])!=c)
		return 0;
	return 1;
}

int main()
{
	freopen("reguli.in","r",stdin);
	freopen("reguli.out","w",stdout);

	scanf("%lld",&n);
	for (i=0;i<n;i++)
		scanf("%lld",a+i);
	for (i=n-1;i>0;i--)
		a[i]=a[i]-a[i-1];
	a[0]=0;
	--n;
	pref();

	sol=1;
	while (!ok(sol))
		++sol;

	printf("%lld\n",sol);
	for (i=1;i<=sol;i++)
		printf("%lld\n",a[i]);

	return 0;
}