Pagini recente » Cod sursa (job #119370) | Cod sursa (job #1193156) | Cod sursa (job #696958) | Cod sursa (job #1130313) | Cod sursa (job #309926)
Cod sursa(job #309926)
#include<cstdio>
using namespace std;
#define MAX_N 500003
long long unsigned A[MAX_N];
int pi[MAX_N];
bool ok[MAX_N];
int N;
void read()
{
freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
scanf("%d",&N);
long long unsigned cr, ant;
int i;
scanf("%llu",&ant);
--N;
for(i=1;i<=N;++i)
{
scanf("%llu",&cr);
A[i] = cr - ant;
ant = cr;
}
}
void make_prefix()
{
int i,k;
pi[1] = 0; k = 0;
for(i=2;i<=N;++i)
{
while(k && A[k+1] != A[i]) k = pi[k];
if(A[k+1] == A[i]) ++k;
pi[i] = k;
}
}
void make_ok()
{
int k = N;
ok[0] = true;
while(k)
{
ok[k] = 1;
k = pi[k];
}
}
void solve()
{
int c,r;
int L,i;
for(L = 1; L <= N; ++ L)
{
r = N % L; c = N / L;
if(pi[N-r] == 0) continue;
if( (N-r) % ( N - r - pi[N-r] ) ) continue;
if( (N-r) / ( N - r - pi[N-r]) != c) continue;
if(!ok[r]) continue;
printf("%d\n",L);
break;
}
if(L == N+1) { L = N; printf("%d\n",N); }
for(i=1;i<=L;++i) printf("%d\n",A[i]);
}
int main()
{
read();
make_prefix();
make_ok();
solve();
return 0;
}