Pagini recente » Cod sursa (job #392846) | Cod sursa (job #613312) | Cod sursa (job #1335150) | Cod sursa (job #2044606) | Cod sursa (job #309912)
Cod sursa(job #309912)
#include <fstream.h>
#define MaxN 500005
long long n,d[MaxN],pi[MaxN],ok[MaxN],L;
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;
}
}
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)
L=i;
}
}
void afis()
{
int i;
ofstream fout("reguli.out");
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;
}