Pagini recente » Cod sursa (job #1603077) | Cod sursa (job #2194937) | Cod sursa (job #1286154) | Cod sursa (job #1912924) | Cod sursa (job #2816880)
// O(N) time and memory
#include <stdio.h>
#include <string.h>
#define ll long long
#define NMax 500005
int N;
ll v[NMax]; int pi[NMax], ok[NMax];
void functie_prefix(void)
{
int i, k;
pi[1] = 0; k = 0;
for (i = 2; i <= N; i++)
{
while (k > 0 && v[k+1] != v[i])
k = pi[k];
if (v[k+1] == v[i])
k++;
pi[i] = k;
}
}
ll extract(void)
{
int i, l;
ll x = 0;
char s[32];
fgets(s, sizeof(s), stdin);
l = strlen(s);
for (i = (s[0]=='-'); i < l; i++)
if (s[i] >= '0' && s[i] <= '9')
x = x * 10 + (s[i] - '0');
else
break;
if (s[0] == '-') x = -x;
return x;
}
int main(void)
{
int i, K, c, r, sol = 0;
ll x, ant;
freopen("reguli.in", "r", stdin);
freopen("reguli.out", "w", stdout);
scanf("%d\n", &N);
ant = extract();
for (i = 2; i <= N; i++)
{
x = extract();
v[i-1] = x-ant;
ant = x;
}
N--;
functie_prefix();
for (r = N; r; r = pi[r])
ok[pi[r]] = 1;
for (K = 1; K <= N; K++)
{
c = N / K; r = N % K;
if (pi[N-r] > 0 && (N-r) % (N-r-pi[N-r]) == 0 &&
(N-r) / (N-r-pi[N-r]) == c && ok[r])
{ sol = 1; break; }
}
if (!sol) K--;
printf("%d\n", K);
for (i = 1; i <= K; i++)
printf("%lld\n", v[i]);
return 0;
}