Cod sursa(job #3353111)

Utilizator Grama2008Grama Andrei Teodor Grama2008 Data 4 mai 2026 21:35:55
Problema Curcubeu Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

const int N=1e6+5, mod=1e9+7, C=1;
const long long INF=1e18;
//#define int long long

int color[N], parent[N], n, a, b, c;

int findparent(int x) {
    if (parent[x]==x) {
        return x;
    }
    return parent[x]=findparent(parent[x]);
}

long long lgpow(long long a, int b) {
    long long res=1;
    while (b) {
        if (b&1) {
            res=res*a%n;
        }
        a=a*a%n;
        b>>=1;
    }
    return res;
}

void unite(int a, int b) {
    parent[a]=b;
}

void solve_testcase() {
    cin>>n>>a>>b>>c;
    for (int i=1;i<=n;i++) {
        parent[i]=i;
    }
    for (int i=2;i<n;i++) {
        a=(a*i)%n;
        b=(b*i)%n;
        c=(c*i)%n;
    }
    for (int i=n-1;i>=1;i--) {
        int l=min(a, b), r=max(a, b);
        l=findparent(l);
        while (l<=r) {
            color[l]=c;
            unite(l,l+1);
            l=findparent(l);
        }
        int invmod=lgpow(i, n-2);
        a=1LL*a*invmod%n;
        b=1LL*b*invmod%n;
        c=1LL*c*invmod%n;
    }
    for (int i=1;i<n;i++) {
        cout<<color[i]<<'\n';
    }
}

signed main() {
    freopen("curcubeu.in", "r", stdin);
    freopen("curcubeu.out", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t=1;
    //cin>>t;
    while (t--) {
        solve_testcase();
    }
    return 0;
}