Codeforces Round #421 (Div. 2), problem: (E) Mister B and Beacons on Field Solution In C/C++

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.util.TreeMap;

/**
* @author Don Li
*/
public class MisterBBeaconsField {

int N = (int) 2e6 + 10;
int SQRT = (int) (Math.sqrt(N) + 0.5);

int[] f = new int[N];
long nn, mm, ss;

long ans;
int[][] fs;
List<Long> bad = new ArrayList<>();

void solve() {
for (int i = 2; i < N; i++) {
if (f[i] == 0) {
f[i] = i;
for (int j = i * i; j < N && i <= SQRT; j += i) f[j] = i;
}
}

int T = in.nextInt();
while (T– > 0) {
int[] n = new int[3], m = new int[3], s = new int[3];
for (int i = 0; i < 3; i++) n[i] = in.nextInt();
for (int i = 0; i < 3; i++) m[i] = in.nextInt();
for (int i = 0; i < 3; i++) s[i] = in.nextInt();

s[0] *= 2;
nn = (long) n[0] * n[1] * n[2];
mm = (long) m[0] * m[1] * m[2];
ss = (long) s[0] * s[1] * s[2];

ans = 0;

fs = primeFactors(s);
dfs(0, 1);

bad.clear();
int[][] fn = primeFactors(n);
for (int i = 0; i < fn.length; i++) {
long v = fn[i][0];
for (int j = 0; j < fn[i][1]; j++) {
if (ss % v != 0) {
bad.add(v);
break;
}
v *= fn[i][0];
}
}
dfs2(0, 1, 0);

out.println(ans);
}
}

// iterate all the divisors of 2*s and count the number of divisors ≤ n
void dfs(int i, long v) {
if (i == fs.length) {
if (v <= nn) ans++;
return;
}
long mul = 1;
for (int j = 0; j <= fs[i][1]; j++) {
dfs(i + 1, v * mul);
mul *= fs[i][0];
}
}

// calc the number of k (such that gcd(n,k) | 2*s and 1≤k≤m) with inclusion-exclusion principle
void dfs2(int i, long v, int cnt) {
if (i == bad.size()) {
if (cnt == 0) ans += mm / v;
else ans -= mm / v;
return;
}
dfs2(i + 1, v, cnt);
dfs2(i + 1, v * bad.get(i), cnt ^ 1);
}

int[][] primeFactors(int[] a) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < 3; i++) {
int x = a[i];
while (x > 1 && x != f[x]) {
map.put(f[x], map.getOrDefault(f[x], 0) + 1);
x /= f[x];
}
if (x > 1) map.put(x, map.getOrDefault(x, 0) + 1);
}

int k = map.keySet().size();
int[][] cnt = new int[k][2];
int p = 0;
for (int x : map.keySet()) {
cnt[p][0] = x;
cnt[p][1] = map.get(x);
p++;
}
return cnt;
}

public static void main(String[] args) {
in = new FastScanner(new BufferedReader(new InputStreamReader(System.in)));
out = new PrintWriter(System.out);
new MisterBBeaconsField().solve();
out.close();
}

static FastScanner in;
static PrintWriter out;

static class FastScanner {
BufferedReader in;
StringTokenizer st;

public FastScanner(BufferedReader in) {
this.in = in;
}

public String nextToken() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(in.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

public int nextInt() {
return Integer.parseInt(nextToken());
}

public long nextLong() {
return Long.parseLong(nextToken());
}

public double nextDouble() {
return Double.parseDouble(nextToken());
}
}
}