Pagini recente » Cod sursa (job #461592) | Cod sursa (job #1334742) | Cod sursa (job #949977) | Cod sursa (job #380933) | Cod sursa (job #1561789)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("reguli.in");
ofstream out("reguli.out");
const int MAX_N = 500000;
int n;
long long V[1 + MAX_N];
long long D[1 + MAX_N];
int PI[1 + MAX_N];
bool equalPrefSuf[1 + MAX_N];
bool testLength(int L) {
int k = n / L, r = n % L;
return(PI[n - r] > 0 &&
(n - r) % (n - r - PI[n - r]) == 0 &&
(n - r) / (n - r - PI[n - r]) == k &&
equalPrefSuf[r]);
}
int main() {
int i, l, q;
in >> n >> V[0];
n--;
for(i = 1; i <= n; i++) {
in >> V[i];
D[i] = V[i] - V[i - 1];
}
for(i = 2, q = 0; i <= n; i++) {
while(q > 0 && D[q + 1] != D[i]) q = PI[q];
if(D[q + 1] == D[i]) q++;
PI[i] = q;
}
for(q = PI[n]; q > 0; q = PI[q]) {
equalPrefSuf[q] = true;
}
for(l = 1; l <= n && testLength(l) == false; l++);
if(l > n) l--;
out << l << '\n';
for(i = 1; i <= l; i++) {
out << V[i] - V[i - 1] << '\n';
}
return 0;
}