Cod sursa(job #1516969)

Utilizator Burbon13Burbon13 Burbon13 Data 3 noiembrie 2015 19:08:44
Problema Reguli Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <cstdio>

using namespace std;

const int nmx = 500002;

int n,pr[nmx];
long long v[nmx];

void citire(){
    long long a,b;
    scanf("%d", &n);
    scanf("%lld", &b);
    for(int i = 2; i <= n; ++i){
        scanf("%lld", &a);
        v[i-2] = a - b;
        b = a;
    }
}

void prefix(){
    int i = 1, j = 0;
    while(i < n - 1){
        if(v[i] != v[j])
            if(j)
                j = pr[j-1];
            else
                ++ i;
        else{
            pr[i] = j + 1;
            ++ i;
            ++ j;
        }
    }
}

int calcc(){
    for(int i = n - 2; i >= 0; --i)
        if((i+1) % (i + 1 - pr[i]) == 0)
            return i + 1 - pr[i];
}

int main(){
    freopen("reguli.in", "r", stdin);
    freopen("reguli.out", "w", stdout);

    citire();
    prefix();

    int val = calcc();
    printf("%d\n",val);
    for(int i = 0; i < val; ++i)
        printf("%d\n", v[i]);

    return 0;
}