Educational Codeforces Round 110 (Rated for Div. 2)B. Array Reodering

给一个数组, 可以reorder这个数组, 求最大数量的pair, 使得gcd(ary[i], ary[j] * 2) >1 where i < j.

这个题就是需要思考, 我暴力的求解了一下, 发现过不了. 这题求一个数和2个倍数的gcd的大于1(非互质)个数. 因为能无限制reorder, 所以主要看这个数是不是2的倍数, 即是否可以被2整除, 如果可以, 假如ary[i] = 4, 那么肯定和 ary[j] * 2的gcd>1, 无论ary[j]是多少.

所以把数字分成两类, 一类是2的倍数, 另一类是非2的倍数, 然后排序下, 找一边即可.

package readman;
import net.egork.generated.collections.*;
import net.egork.generated.collections.list.IntArrayList;
import net.egork.io.InputReader;
import net.egork.io.OutputWriter;

import java.util.*;

import static net.egork.numbers.IntegerUtils.gcd;

public class TaskB {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int k = in.readInt();
        for (int i = 0; i < k; i++) {
            int f = in.readInt();
            out.printLine(solve(in.readIntArray(f)));
        }
    }

    private int solve(int[] arr) {
        int count = 0;
        List<Integer> l1 = new ArrayList<>();
        List<Integer> l2 = new ArrayList<>();
        for(int a : arr){
            if(a % 2 == 0)
                l2.add(a);
            else
                l1.add(a);
        }
        Collections.sort(l1, Collections.reverseOrder());
        Collections.sort(l2, Collections.reverseOrder());
        List<Integer> list = new ArrayList<>();
        list.addAll(l2);
        list.addAll(l1);
        for (int i = 0; i < list.size(); i++) {
            for (int j = i + 1; j < list.size(); j++) {
                if (gcd(list.get(i), list.get(j) * 2) > 1)
                    count++;
            }
        }
        return count;
    }

}