Cod sursa(job #464900)

Utilizator S7012MYPetru Trimbitas S7012MY Data 22 iunie 2010 14:35:04
Problema Curcubeu Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <cstdio>
#include <algorithm>
using namespace std;
#define DN 1000010

int s[DN],urm[DN],a[DN],b[DN],c[DN],n;

int drum(int el) {
	int i,j;
	for(i=el; s[el]; el=urm[el]);
	while(s[i]) {
		j=i;
		i=urm[i];
		urm[j]=el;
	}
	return el;
}

int main()
{
	int i,j,x;
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d %d %d %d",&n,&a[0],&b[0],&c[0]);
	for(i=1; i<=n; i++) {
		a[i]=(1LL*a[i-1]*i)%n;
		b[i]=(1LL*b[i-1]*i)%n;
		c[i]=(1LL*c[i-1]*i)%n;
		urm[i]=i+1;
		s[i]=-1;
		if(a[i]>b[i]) swap(a[i],b[i]);
	}
	for(i=n-1;i>=1;i--) {
		for(int j=a[i];j<=b[i];) {
			if(s[j]==-1){
				s[j]=c[i];
			}
			x=j;
			j=urm[j];
			urm[x]=b[i]+1;
		}
	}
	for (i=1;i<n;i++)
		if(s[i]==-1) printf("0\n");
		else printf("%d\n",s[i]);
	return 0;
}