fork download
copy 
  1. import java.util.*;
  2.  
  3. class Codechef {
  4.     static final int N = 200000;
  5.     static ArrayList<Integer>[] div = new ArrayList[N];
  6.  
  7.     static {
  8.         pre();
  9.     }
  10.     static void pre() {
  11.         for (int i = 0; i < N; i++) div[i] = new ArrayList<>();
  12.         for (int i = 2; i < N; i++)
  13.             for (int j = i; j < N; j += i)
  14.                 div[j].add(i);
  15.     }
  16.  
  17.     public static void main(String[] args) {
  18.         Scanner sc = new Scanner(System.in);
  19.         int t = sc.nextInt();
  20.         while (t-- > 0) {
  21.             int n = sc.nextInt();
  22.             int[] A = new int[n]; 
  23.             int[] B = new int[n]; // cost
  24.             for (int i = 0; i < n; i++){
  25.                 A[i] = sc.nextInt();
  26.             }
  27.             for (int i = 0; i < n; i++){
  28.                 B[i] = sc.nextInt();
  29.             }
  30.             System.out.println(gcd(A,B));
  31.         }
  32.         sc.close();
  33.     }
  34.  
  35.     public static int gcd(int[] a, int[] b) {
  36.         int n = a.length;
  37.         HashSet<Integer> map = new HashSet<>();
  38.         for (int x : a) {
  39.             for (int p : div[x]) {
  40.                 if (map.contains(p)) return 0; // no ops needed....
  41.                 map.add(p);
  42.             }
  43.         }
  44.         HashMap<Integer, Integer> cnt = new HashMap<>();
  45.         for (int x : a)
  46.             for (int p : div[x])
  47.                 cnt.put(p, cnt.getOrDefault(p, 0) + 1);
  48.         for (int i = 0; i < n; i++) {
  49.             int x = a[i];
  50.             for (int p : div[x])
  51.                 cnt.put(p, cnt.get(p) - 1);
  52.             int y = x + b[i];
  53.             for (int p : div[y])
  54.                 if (cnt.getOrDefault(p, 0) > 0)
  55.                     return 1; // when case of making 1 e to o or 1 o to e...
  56.             for (int p : div[x])
  57.                 cnt.put(p, cnt.get(p) + 1);
  58.         }
  59.         return 2;  // when case of making 2 odds to even
  60.     }
  61. }
  62.  
Success #stdin #stdout 0.71s 113076KB
comments (?)
stdin
copy 
6
2
1 1
1 1
2
4 8
1 1
5
1 1 727 1 1
1 1 1 1 1
2
3 11
1 1
3
2 7 11
1 1 1
3
7 12 13
1 1 1
stdout
copy 
2
0
2
1
1
1
https://ideone.com/ZhvnTZ
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!