Cod sursa(job #277692)

Utilizator tvladTataranu Vlad tvlad Data 11 martie 2009 20:56:36
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.04 kb
#include <cstdio>

const int NMAX = 1000000;

int n;
int a[NMAX], b[NMAX], c[NMAX];
int v[NMAX], skip[NMAX];

int next ( int k )  {
	if (k >= n)
		return k;
	if (skip[k] != k) {
		int nx, aux, r;
		for (nx = k, aux = 0; skip[nx] != nx && aux < n; nx = skip[nx], ++aux);
		if (aux == n)
			return -1;
		for (r = k; skip[r] != r; aux = skip[r], skip[r] = nx, r = aux);
		return nx;
	} else {
		return k;
	}
}

int main() {
	freopen("curcubeu.in","rt",stdin);
	freopen("curcubeu.out","wt",stdout);
	scanf("%d %d %d %d",&n,&a[1],&b[1],&c[1]);
	if (n < 10) return 0;
	for (int i = 2; i < n; ++i) {
		a[i] = (a[i-1] * i) % n;
		b[i] = (b[i-1] * i) % n;
		c[i] = (c[i-1] * i) % n;
	}
	--n;

	for (int i = 0; i < n; ++i) skip[i] = i;
	for (int k = n; k > 0; --k) {
		if (b[k] < a[k])
			a[k] ^= b[k] ^= a[k] ^= b[k];
		int i;
		for (i = next(a[k]-1); i < b[k] && i != -1; i = skip[i]) {
			v[i] = c[k];
			skip[i] = next(i+1);
		}
		if (i == -1) break;
	}

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