Pagini recente » Cod sursa (job #1580710) | Cod sursa (job #896611) | Cod sursa (job #2898219) | Cod sursa (job #2202018) | Cod sursa (job #2637097)
#include <bits/stdc++.h>
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int Nmax = 5e5 + 5;
int N, cat, rest;
int pi[Nmax];
long long delta[Nmax];
long long x, y;
void make_prefix()
{
int K = 0;
for(int i = 2; i < N; ++i)
{
while(K && delta[K + 1] != delta[i])
K = pi[K - 1];
if(delta[K + 1] == delta[i])
K++;
pi[i] = K;
}
}
int main()
{
in >> N >> x;
for(int i = 1; i < N; ++i)
{
in >> y;
delta[i] = y - x;
x = y;
}
make_prefix();
int ans = 0;
for(int L = 1; L < N && !ans; ++L)
{
cat = N / L;
rest = N % L;
if(pi[N - rest] &&
(N - rest) % (N - rest - pi[N - rest]) == 0 &&
(N - rest) / (N - rest - pi[N - rest]) == cat)
{
int k = 1;
for(int j = N - rest + 1; j < N && k; ++j, ++k)
if(delta[j] != delta[k])
k = 0;
if(k)
ans = L;
}
}
out << ans << '\n';
for(int i = 1; i <= ans; ++i)
out << delta[i] << '\n';
return 0;
}