Cod sursa(job #657934)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 7 ianuarie 2012 17:19:37
Problema Curcubeu Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.97 kb
#include <fstream>
#define NMAX 1000001

using namespace std;

ifstream f("curcubeu.in");
ofstream g("curcubeu.out");

int n,a[NMAX],b[NMAX],c[NMAX],PR[NMAX],v[NMAX],i;

inline int rad(int x) {
    int p,y;
    for (p=x;p!=PR[p];p=PR[p]);
    for (;x!=PR[x];) {
        y=PR[x];
        PR[x]=p;
        x=y;
    }
    return p;
}
inline void unite(int x,int y) {
    if (x>y) PR[y]=x;
        else PR[x]=y;
}
int main () {
    f >> n >> a[1] >> b[1] >> c[1];
    PR[1]=1;PR[n]=n;
    if (a[1]>b[1]) swap(a[1],b[1]);
    for (i=2;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;
        if (a[i]>b[i]) swap(a[i],b[i]);
        PR[i]=i;
    }
    for (i=n-1;i>=1;i--)
        for (a[i]=rad(a[i]);a[i]<=b[i];a[i]=rad(a[i])) {
            v[a[i]]=c[i];
            unite(rad(a[i]),rad(a[i]+1));
        }
    for (i=1;i<n;i++)
        g << v[i] << '\n';
    f.close();g.close();
    return 0;
}