Cod sursa(job #360485)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 31 octombrie 2009 17:58:48
Problema Curcubeu Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#define lm 1000010

int a[lm], b[lm], c[lm], t[lm], n, v[lm];

int find (int x)
{
	int c, i;
	for (i=x; t[i]>0; i=t[i]);
	for (; t[x]>0;)
	{
		c=t[x];
		t[x]=i;
		x=c;
	}
	return i;
}

int main()
{
	freopen("curcubeu.in","r",stdin);
	freopen("curcubeu.out","w",stdout);
	scanf("%d %d %d %d",&n, &a[1], &b[1], &c[1]);
	int i,j,k, p;
	for (i=2; i<n; i++) 
	{
		a[i]=(a[i-1]*i)%n;
		b[i]=(b[i-1]*i)%n;
		if (a[i]>b[i])
		{
			j=a[i];
			a[i]=b[i];
			b[i]=j;
		}
		c[i]=(c[i-1]*i)%n;
	}
	for (j=n-1; j>0; j--)
	{
		p=i-1;
		for (i=a[j]; i<=b[j]+1; i++)
		{
			if (v[i])
			{	
				k=find(i)+1;
				if (i>a[j] && t[p]==0)
				{
					if (k<=b[j]) 
						t[p]=k; else
							t[p]=-c[j];
				}
				v[i-1]=1;
				i=k;
			} else
			{
				if (i>a[j] && !v[p]) 
				{
					t[p]=i;
					if (i>b[j]) t[p]=-c[j];
					v[p]=1;
				}
			p=i;
			}
		}
	}
	for (i=1; i<n; i++)
		printf("%d\n",0-t[find(i)]);
}