Pagini recente » Cod sursa (job #2815092) | Cod sursa (job #2392121) | Cod sursa (job #1108344) | Cod sursa (job #1490392) | Cod sursa (job #309925)
Cod sursa(job #309925)
#include <fstream.h>
#define MaxN 500005
long long n,d[MaxN],pi[MaxN],ok[MaxN],L,x;
void cit()
{
int i,a,b;
ifstream fin("reguli.in");
fin>>n>>a;
for(i=1;i<n;i++)
{
fin>>b;
d[i]=b-a;
a=b;
}
}
void prefix()
{
int k=0,i;
for(i=2;i<n;i++)
{
while(k && d[k+1]!=d[i])
k=pi[k];
if(d[k+1]==d[i])
k++;
pi[i]=k;
if(k && i%(i-k)==0)
x=k;
}
}
void OK()
{
int k;
n--;
k=pi[n];
while(!ok[k])
{
ok[k]=1;
k=pi[k];
}
}
void perioada()
{
int i,r,c;
for(i=1;i<=n;i++)
{
r=n%i;
c=n/i;
if(pi[n-r] && (n-r)%(n-r-pi[n-r])==0 && (n-r)/(n-r-pi[n-r])==c && ok[r])
L=i;
}
}
void afis()
{
int i;
ofstream fout("reguli.out");
/*for(i=1;i<=n;i++)
fout<<d[i]<<" ";
fout<<'\n';*/
if(L==0)
L=n;
fout<<L<<'\n';
for(i=1;i<=L;i++)
fout<<d[i]<<'\n';
fout.close();
}
int main()
{
cit();
prefix();
OK();
perioada();
afis();
return 0;
}