Pagini recente » Cod sursa (job #813550) | Cod sursa (job #1738458) | Cod sursa (job #525029) | Cod sursa (job #1986626) | Cod sursa (job #216854)
Cod sursa(job #216854)
#include <cstdio>
#include <bitset>
using namespace std;
#define MAX_N 500007
int N;
long long V[MAX_N], S[MAX_N];
long long pi[MAX_N];
bitset <MAX_N>ok;
void citire()
{
scanf("%d\n",&N);
for(int i = 0; i < N; ++i)
scanf("%d", V+i);
--N;
}
void kmp()
{
int i, q = 0;
for(i = 2, pi[1] = 0; i <= N; ++i)
{
while(q && S[q+1] != S[i])
q = pi[q];
if(S[q+1] == S[i])
++q;
pi[i] = q;
}
q = N;
while(q)
{
q = pi[q];
ok[q] = 1;
}
}
void solve()
{
for(int i = 1; i <= N; ++i)
S[i] = V[i] - V[i-1];
int L = (N >> 1), i;
kmp();
for(i = 1; i <= L; ++i)
{
int r = N % i;
int c = N / i;
int pN = N - r;
if(pi[pN] && (pN % (pN - pi[pN]) == 0) && ((pN / (pN - pi[pN])) % c == 0) && ok[r])
break;
}
if(i <= L)
{
printf("%d\n", i);
for(int j = 1; j <= i; ++j)
printf("%d\n", S[j]);
return;
}
for(i = L + 1; i <= N; ++i)
{
int r = N % i;
int pN = N -r;
if(pi[pN] && ok[r])
break;
}
printf("%d\n", i);
for(int j = 1; j <= i; ++j)
printf("%d\n", S[j]);
}
int main()
{
freopen("reguli.in","rt",stdin);
freopen("reguli.out","wt",stdout);
citire();
solve();
}