Beta Round #56-C: Mushroom Strife

keyword

整数　最大公約数　最小公倍数　C++

問題概要

ノード数V(<100)のグラフがあり、各頂点には番号が割り振られている。E組の頂点間に関しては最大公約数と最小公倍数が指定されている(どちらもN=10^6以下)。全ての制約を満たす番号の割り振りがあるかどうか判定する問題。ある場合にはその一例を出力する。

解法

lcm(a,b)=a*b/gcd(a,b)なのである頂点間についてはa*bの値が分かる。なのである頂点の値(a*b = gcd*lcm の約数)を固定すればその頂点を含む連結成分については他の頂点の値を全て決定できる。後は制約を満たすかどうか判定すれば良い。計算量O(sqrt(N^2) + log N * V*E) = O(N + log N * V*E)。

感想

コンテスト中は思いつかなかったので終了後に他の人のコードを見て通した。基本的には「全探索 -> Greedy」を最初に考えるようにしているはずなのに気付かなかったのは要反省。あと、配列にfixedという名前を付けたらコンパイラさんに怒られた。

const int MAX_N = 102;
int64 gcd[MAX_N][MAX_N];
int64 lcm[MAX_N][MAX_N];
bool visited[MAX_N];
bool fixedd[MAX_N];
int64 ans[MAX_N];
int N;

int64 __lcm(int64 a, int64 b){ return a*b/__gcd(a,b); }

void dfs2(int v){
    fixedd[v] = true;
    for(int i=0; i<N; i++)if(gcd[v][i] && !fixedd[i]){
        dfs2(i);
    }
}

bool dfs(int v){
    visited[v] = true;
    for(int i=0; i<N; i++)if(gcd[v][i] && !visited[i]){
        if(lcm[v][i]*gcd[v][i]%ans[v] != 0) return false;
        ans[i] = lcm[v][i]*gcd[v][i]/ans[v];
        dfs(i);
    }
    return true;
}

bool check(int v){
    visited[v] = true;
    for(int i=0; i<N; i++)if(gcd[v][i]){
        if(!(__gcd(ans[v],ans[i]) == gcd[v][i] && __lcm(ans[v],ans[i]) == lcm[v][i])){
            return false;
        }
        if(!visited[i] && !check(i)) return false;
    }
    return true;
}

void solve(){
    for(int i=0; i<N; i++)if(!fixedd[i]){
        int64 multi = -1;
        for(int j=0; j<N; j++)if(i!=j && gcd[i][j]){
            multi = gcd[i][j]*lcm[i][j];
        }
        if(multi == -1){
            fixedd[i] = true;
            ans[i] = 1;
            continue;
        }
        bool found = false;
        for(int j=1; j*j<=multi; j++)if(multi%j==0){
            ans[i] = j;
            memset(visited, 0, sizeof(visited));
            if(dfs(i)){
                memset(visited,0,sizeof(visited));
                if(check(i)){
                    dfs2(i);
                    found = true;
                    break;
                }
            }
            ans[i] = multi/j;
            memset(visited, 0, sizeof(visited));
            if(dfs(i)){
                memset(visited,0,sizeof(visited));
                if(check(i)){
                    dfs2(i);
                    found = true;
                    break;
                }
            }
        }
        if(!found){
            puts("NO");
            return ;
        }
    }
    puts("YES");
    for(int i=0; i<N; i++){
        cout << ans[i];
        cout << (i==N-1?'\n':' ');
    }
    return ;
}

int main(){
    int M;
    scanf("%d%d",&N,&M);
    for(int i=0; i<M; i++){
        int x, y, g, l;
        scanf("%d%d%d%d",&x,&y,&g,&l);
        gcd[x-1][y-1] = gcd[y-1][x-1] = g;
        lcm[x-1][y-1] = lcm[y-1][x-1] = l;
    }
    solve();
    return 0;
}