Pagini recente » Cod sursa (job #248538) | Cod sursa (job #2004128) | Cod sursa (job #1111746) | Cod sursa (job #1900182) | Cod sursa (job #496730)
Cod sursa(job #496730)
#include <stdio.h>
#define NMAX 500005
#define ll long long
int n,r,pi[NMAX],rez;
ll A[NMAX],B[NMAX];
char marc[NMAX];
void read()
{
scanf("%d",&n);
int i;
for (i=1; i<=n; i++)
scanf("%lld",&A[i]);
for (i=2; i<=n; i++)
B[++r]=A[i]-A[i-1];
}
void prefix()
{
int i,q=0;
for (i=2; i<=r; i++)
{
while (B[q+1]!=B[i] && q>0)
q=pi[q];
if (B[q+1]==B[i]) q++;
pi[i]=q;
}
}
void precompute()
{
int i,q=pi[r];
marc[0]=1;
while (q)
{
marc[q]=1;
q=pi[q];
}
}
int solve()
{
int i,p,q,s;
prefix();
precompute();
for (i=1; i<=r; i++)
{
p=r/i; q=r%i; s=p*i;
if (s%(s-pi[s])==0 && pi[s]>0 && pi[s]==s-i && marc[q])
return i;
}
return r;
}
int main()
{
freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
read();
rez=solve();
printf("%d\n",rez);
for (int i=1; i<=rez; i++)
printf("%lld\n",B[i]);
return 0;
}