Pagini recente » Cod sursa (job #2522575) | Cod sursa (job #523792) | Cod sursa (job #1886284) | Cod sursa (job #1168727) | Cod sursa (job #23275)
Cod sursa(job #23275)
#include <stdio.h>
#define NMAX 500001
int N;
unsigned long long A[NMAX];
long long AA[NMAX];
int pi[NMAX];
void prefix()
{
int q = 0;
pi[1] = 0;
for (int i = 2; i<=N; ++i)
{
while (q && AA[q+1] != AA[i])
q = pi[q];
if (AA[q+1] == AA[i])
++q;
pi[i] = q;
}
}
int main()
{
freopen("reguli.in", "r", stdin);
freopen("reguli.out", "w", stdout);
scanf("%d", &N);
for (int i = 1; i<=N; ++i)
{
scanf("%lld", &A[i]);
}
--N;
for (int i = 1; i<=N; ++i)
{
AA[i] = A[i+1]-A[i];
}
prefix();
--N;
int min = N;
for (int L = 1; L<=N; ++L)
{
int c = N/L;
int r = N%L;
int d1 = N-r;
int d2 = pi[N-r];
if (d2>0 && d1 % (d1-d2) == 0 && (d1) / (d1-d2) == c)
{
min = L;
break;
}
}
printf("%d\n", min);
for (int i = 1; i<=min; printf("%lld\n", AA[i]), ++i);
}