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;
}
}