Pagini recente » Cod sursa (job #390772) | Cod sursa (job #2313575) | Cod sursa (job #622356) | Cod sursa (job #375241) | Cod sursa (job #2089897)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
const int NMAX = 500000 + 5;
const int INF = 0x3f3f3f3f;
int n, len, period, minim = INF;
int v[NMAX], phi[NMAX];
void prefix()
{
for (int i = 2; i <= len; ++i)
{
int last = phi[i - 1];
while (last > 0 && v[i] != v[last + 1]) last = phi[last];
if (v[i] == v[last + 1]) phi[i] = last + 1;
}
}
void write()
{
if (period)
{
fout << period << '\n';
for (int i = 1; i <= period; ++i)
fout << v[i] << '\n';
}
else
{
fout << len << '\n';
for (int i = 1; i <= len; ++i)
fout << v[i] << '\n';
}
}
void read()
{
int x1, x2;
fin >> n >> x1;
for (int i = 2; i <= n; ++i)
{
fin >> x2;
v[++len] = x2 - x1;
x1 = x2;
}
}
int main()
{
read();
prefix();
for (int i = 1; i <= len; ++i)
if (i % (i - phi[i]) == 0 && phi[i]) //prefixul i e periodic
minim = min(minim, i - phi[i]);
write();
return 0;
}