Pagini recente » Cod sursa (job #1683689) | Cod sursa (job #1979674) | Cod sursa (job #1891854) | Cod sursa (job #2441142) | Cod sursa (job #40405)
Cod sursa(job #40405)
#include <stdio.h>
#include <string.h>
#define nmax 500005
long n, p[nmax];
long long int s[nmax];
void read();
void prefix();
void prefixmare();
int main()
{
memset(p,0,sizeof(p));
memset(s,0,sizeof(s));
read();
prefix();
prefixmare();
return 0;
}
void read()
{
long i;
long long int x,x1;
freopen("regulic.in","r",stdin);
scanf("%ld", &n);
scanf("%lld", &x);
for (i=1; i<n; i++)
{
scanf("%lld", &x1);
s[i] = x1-x;
x=x1;
}
n-=1;
fclose(stdin);
}
void prefix()
{
long q,k;
p[1]=0; k=0;
for (q=2; q<=n; q++)
{
while ( k>0 && s[k+1] != s[q])
k=p[k];
if (s[k+1] == s[q]) k+=1;
p[q]=k;
}
}
void prefixmare()
{
long i,ok;
long long int lmin, max=0;
for (i=2; i<=n; i++)
if ( (p[i] >0) && ( i % (i-p[i])==0 ) )
max=i;
if (max == 0)
{
max = n;
lmin = n;
}
else lmin=max-p[max];
if ((max < n ) && (n-max >= lmin) )
{
lmin = n;
max = n;
}
if ((max < n) && ( n-max < lmin))
{
ok=1;
for (i = max+1; i<=n; i++)
if (s[i] != s[i-max])
{
ok=0;
break;
}
if (ok==0)
{
max=n;
lmin=n;
}
}
freopen("reguli.out","w",stdout);
printf("%lld\n",lmin);
for (i=1; i<=lmin; i++)
printf("%lld\n",s[i]);
fclose(stdout);
}