Cod sursa(job #91698)

Utilizator mariusdrgdragus marius mariusdrg Data 13 octombrie 2007 09:19:06
Problema Curcubeu Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include<stdio.h>

const int maxn = 1000100;

int i;
int g[maxn];
int cul[maxn];
long long n;
long long a1,b1,c1;
int culo[maxn];
int lim1[maxn];
int lim2[maxn];
inline long long max(long long i,long long j)
{
        return i > j ? i : j;
}

inline long long min(long long i,long long j)
{
        return i < j ? i : j;
}

int grupa(int i)
{
        if (g[i] != i)
        {
                g[i] = grupa(g[i]);
        }
        return g[i];
}

void reuniune(int i,int j)
{
        g[grupa(i)]  = grupa(j);
}



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

        scanf("%lld %lld %lld %lld",&n,&a1,&b1,&c1);

        for(i = 1;i <= n; ++i)
        {
                g[i] = i;
        }
        
        for(i =  1;i < n; ++i)
        {
                a1 = (long long)((long long)a1 * (long long)i) % n;
                b1 = (long long)((long long)b1 * (long long)i) % n;
                c1 = (long long)((long long)c1 * (long long)i) % n;
                lim1[i] = min(a1,b1);
                lim2[i] = max(a1,b1);
                culo[i] = c1;
        }
        for(i = n;i;--i)
        {
                c1 = culo[i];
                lim1[i] = grupa(lim1[i]);
                while(lim1[i] <= lim2[i])
                {
                        cul[lim1[i]] = c1;
                        if (lim1[i] < n) reuniune(lim1[i],lim1[i] + 1);
                        lim1[i] = grupa(lim1[i]);
                }
        }

        for(i = 1;i < n; ++i)
        {
                printf("%d\n",cul[i]);
        }

        return 0;
}