B - GCD Sequence AtCoder Grand Contest 022

B - GCD Sequence

問題概略
要素数がNで互いに異なる整数であり、どの要素もそれ以外の合計との最大公約数が1ではなく、すべての要素の最大公約数が1であり、すべては30000以下である物を求めよ
3<=N<=20000;

解法
ある要素とそれを除く要素の合計の最大公約数と、ある要素と全体の合計の最大公約数は等しい。
よって、すべての要素の最大公約数が1であり、すべての要素に対して全体の合計の最大公約数が1で無いものを考えれば良い。
そう考えると、合計に対して全要素に約数をもたせたいと考えたくなる。しかし、全体の最大公約数を1にするため、約数は2種類必要だとわかる。小さい方がいいので2,3を使いたくなるが、制約的にもうまくいく
あとは2,3の倍数を全体の合計が6になるように入れれば良い。

    public static void solve() throws Exception {
        //longを忘れるなオーバーフローするぞ
        N = ni();
        if (N < 7) {
            sol(N);
            return;
        }
        ArrayList<Integer> s = new ArrayList<>();
        s.add(2);
        s.add(3);
        s.add(4);
        for (int i = 1; i < N / 4 + 10; i++) {
            s.add(i * 6 + 0);
            s.add(i * 6 + 2);
            s.add(i * 6 + 3);
            s.add(i * 6 + 4);
        }
        while (s.size() > N) {
            s.remove(s.size() - 1);
        }
        long sum = sum(s);
        if (sum % 6 == 2) {
            s.remove(4);
            s.add(30000);
        } else if (sum % 6 == 3) {
            s.remove(5);
            s.add(30000);
        } else if (sum % 6 == 4) {
            s.remove(6);
            s.add(30000);
        } else if (sum % 6 == 5) {
            s.remove(4);
            s.add(30000 - 6 + 3);
        }
        for (int i = 0; i < N - 1; i++) {
            System.out.print(s.get(i) + " ");
        }
        System.out.println(s.get(N - 1));
    }

    public static void sol(int n) {
        if (n == 3) {
            System.out.println("2 5 63");
        } else if (n == 4) {
            System.out.println("2 5 20 63");
        } else if (n == 5) {
            System.out.println("2 3 4 6 9");
        } else if (n == 6) {
            System.out.println("2 3 4 6 9 12");
        }
    }