Cod sursa(job #2554683)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 23 februarie 2020 11:51:27
Problema Reguli Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <fstream>

using namespace std;

typedef long long lint;

ifstream fin("reguli.in");
ofstream fout("reguli.out");

int n;
lint v[500041];
int pr[500041];
bool ok[500041];

int rezero = 0;

void precalc(){
	int q = 0;
	for(int i = 1; i < n; ++i){
		while(v[i] != v[q] && q>0){
			q = pr[q-1];
		}
		if(v[i] == v[q]){
			q++;
		}
		pr[i] = q;
	}
}

void boomer(){
	int q = pr[n-1];
	while(q > 0){
		ok[q] = true;
		q = pr[q-1];
	}
}

int postcalc(){
	for(int i = 1; i <= n; ++i){
		int r = n%i;
		int c = n/i;
		
		int v = n-r;
		if(pr[v-1]>0 && v/(v-pr[v-1]) == c && v%(v-pr[v-1]) == 0 && ok[r]){
			return i;
		}
	}
	return n;
}

int main(){
	fin >> n;n--;
	lint a, b;
	fin >> a;
	for(int i = 0; i < n; ++i){
		b = a;fin >> a;
		v[i] = a-b;
	}
	precalc();
	boomer();
	int sol = postcalc();
	
	fout << sol << "\n";
	for(int i = 0; i < sol; ++i){
		fout << v[i] << "\n";
	}
	
	return 0;
}