Codeforces Round #323 Div2 C: GCD Table

問題

codeforces.com

解法

テーブル上の既に明らかになっているGCDを取り除いた時に最大の数は、必ず元の配列に含まれているはずである。

コード

import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    public void solve() {
	Scanner scanner = new Scanner(System.in);
	int n = scanner.nextInt();
	TreeMap<Integer, Integer> cnt = new TreeMap<>();
	for (int i = 0; i < n * n; ++i) {
	    int x = -scanner.nextInt();
	    Integer value = cnt.get(x);
	    if (value == null) {
		cnt.put(x, 1);
	    } else {
		cnt.put(x, value + 1);
	    }
	}
	scanner.close();

	ArrayList<Integer> ans = new ArrayList<>();
	for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
	    int top = -entry.getKey();
	    while (entry.getValue() > 0) {

		for (int a : ans) {
		    int gcd = -gcd(top, a);
		    cnt.put(gcd, cnt.get(gcd) - 2);
		}

		ans.add(top);
		cnt.put(-top, cnt.get(-top) - 1);
	    }

	}

	for (int i = 0; i < n; ++i) {
	    System.out.print(ans.get(i) + " ");
	}
    }

    public static void main(String[] args) {
	new Main().solve();
    }

    // 最大公約数
    private int gcd(int a, int b) {

	return b == 0 ? a : gcd(b, a % b);
    }
}