Pagini recente » Cod sursa (job #521326) | Cod sursa (job #94343) | Cod sursa (job #3138808) | Cod sursa (job #2499542) | Cod sursa (job #48032)
Cod sursa(job #48032)
#include <cstdio>
using namespace std;
#define NX 500010
long long v[ NX ];
int pi[ NX ];
bool ok[ NX ];
int N, best;
void cit() {
long long x, y;
int i;
scanf( "%d", &N );
for( i = 0; i < N; i++ ) {
scanf( "%lld", &x );
v[i] = x - y;
y = x;
}
}
void calc_pi() {
int i, k;
for( pi[0] = k = -1, i = 1; i < N; pi[i++] = ++k )
while( k >= 0 && v[k+1] != v[i] )
k = pi[k];
}
void calc_ok() {
int k;
for( k = pi[ N-1 ]; k; k = pi[k] )
ok[ k ] = true;
}
inline
void umin( int& x, int y ) {
if( x > y )
x = y;
}
void kmp() {
int k;
best = N - 1;
for( k = 1; k < N; k++ )
if( (pi[k] > 0) && (k % (k - pi[k]) == 0) && ok[ N - 1 - k + pi[k] ] )
umin( best, k - pi[k] );
}
void rez() {
calc_pi();
calc_ok();
kmp();
}
void scr() {
int i;
printf( "%d\n", best );
for( i = 1; i <= best; i++ )
printf( "%lld\n", v[i] );
/*
for( i = 1; i < N; i++ )
printf( "%lld ", v[i] );
printf( "\n" );
for( i = 1; i < N; i++ )
ok[i] ? printf( "1 " ) : printf( "0 " );
*/
}
int main() {
freopen( "reguli.in", "r", stdin );
freopen( "reguli.out", "w", stdout );
cit();
rez();
scr();
return 0;
}