Cod sursa(job #2095751)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 28 decembrie 2017 11:11:55
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <fstream>
# define DIM 500010
using namespace std;
ifstream fin("reguli.in");
ofstream fout("reguli.out");
long long v[DIM],d[DIM],n,s,x,i,j,t,ok;
int main () {
    fin>>n;
    n--;
    for(i=0;i<=n;i++){
        fin>>x;
        v[i]=x-s;
        s=x;
    }
    for(i=2;i<=n;i++){
        while(v[i]!=v[t+1]&&t!=0)
            t=d[t];
        if(v[i]==v[t+1])
            t++;
        d[i]=t;
    }
    for(i=1;i<=n;i++){
        ok=1;
        for(j=2*i;j<=n&&ok;j+=i){
            t=d[j];
            while(t!=i&&t!=0)
                t=d[t];
            if(t!=i)
                ok=0;
        }
        t=d[n];
        while(t!=n%i&&t!=0)
            t=d[t];
        if(t!=n%i)
            ok=0;
        if(ok){
            fout<<i<<"\n";
            for(j=1;j<=i;j++)
                fout<<v[j]<<"\n";
            return 0;
        }
    }
    return 0;
}