Pagini recente » Cod sursa (job #603066) | Cod sursa (job #3147889) | Cod sursa (job #410807) | Cod sursa (job #2982776) | Cod sursa (job #338567)
Cod sursa(job #338567)
#include <stdio.h>
#define nmax 500005
int n, pi [nmax];
bool ok [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;
}
}
void form_ok ()
{
int x=pi [n];
while (x != 0)
{
ok [x]=true;
x=pi [x];
}
}
int rez ()
{
int i, q=0, r, c;
pi [1]=0;
--n;
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 );
}
form_ok ();
if (pi [n] == n-1)
return 1;
for (i=2; i <= n; ++i)
{
r=n%i;
c=n/i;
if (!pi [n-r]) continue;
if (c > 1)
{
if ((n-r)%(n-r-pi [n-r])) continue;
if ((n-r)/(n-r-pi [n-r]) != c) continue;
}
if (!ok [r]) continue;
return i;
}
return n;
}
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;
}