Pagini recente » Cod sursa (job #311380) | Cod sursa (job #2841533) | Cod sursa (job #2755874) | Cod sursa (job #3168538) | Cod sursa (job #182864)
Cod sursa(job #182864)
#include <stdio.h>
#include <bitset>
using namespace std;
long n,i,k,urm[500005],c,r,sol;
long long x,y,d[500005];
bitset <500005>ok;
int main(){
freopen("reguli.in","r",stdin);
freopen("reguli.out","w",stdout);
scanf("%ld",&n);
scanf("%lld",&x);
for (i=2;i<=n;i++){
scanf("%lld",&y);
d[i-1]=y-x;
x=y;
}
//kmp;
n--;
k=0;
urm[1]=0;
for (i=2;i<=n;i++){
while (k>0 && d[k+1]!=d[i])k=urm[k];
if (d[k+1]==d[i])k++;
urm[i]=k;
}
//
ok[0]=1;
k=urm[n];
while (k){
ok[k]=1;
k=urm[k];
}
//
for (i=1;i<=n;i++){
c=n/i;
r=n-c*i;
if (urm[n-r]>0)
if ((n-r)/(n-r-urm[n-r])==c)
if ((n-r)%(n-r-urm[n-r])==0)
if (ok[r])
{sol=i;break;}
}
if (sol==0){
printf("%ld\n",n);
for (i=1;i<=n;i++)
printf("%ld\n",d[i]);
return 0;
}
printf("%ld\n",sol);
for (i=1;i<=sol;i++)
printf("%ld\n",d[i]);
return 0;
}