fork download 
  1. import java.util.*;
  2.  
  3. class Codechef {
  4.     static final int N = 200000;
  5.     static ArrayList<Integer>[] fac = new ArrayList[N];
  6.  
  7.     static {
  8.         pre();
  9.     }
  10.  
  11.     public static void main(String[] args) {
  12.         Scanner sc = new Scanner(System.in);
  13.         int t = sc.nextInt();
  14.         while (t-- > 0) {
  15.             int n = sc.nextInt();
  16.             int[] a = new int[n];
  17.             int[] b = new int[n];
  18.             for (int i = 0; i < n; i++) a[i] = sc.nextInt();
  19.             for (int i = 0; i < n; i++) b[i] = sc.nextInt();
  20.             System.out.println(solve(a, b));
  21.         }
  22.         sc.close();
  23.     }
  24.  
  25.     static void pre() {
  26.         for (int i = 0; i < N; i++) fac[i] = new ArrayList<>();
  27.         for (int i = 2; i < N; i++)
  28.             for (int j = i; j < N; j += i)
  29.                 fac[j].add(i);
  30.     }
  31.  
  32.     static int solve(int[] a, int[] b) {
  33.         int n = a.length;
  34.         HashMap<Integer, Integer> map = new HashMap<>();
  35.         int Ecnt = 0;
  36.         for (int num : a) {
  37.             for (int p : fac[num]) {
  38.                 if (map.containsKey(p)) return 0; // shared factor >1 found
  39.             }
  40.             for (int p : fac[num]) {
  41.                 map.put(p, map.getOrDefault(p, 0) + 1);
  42.             }
  43.             if (num%2 == 0) Ecnt++;
  44.         }
  45.  
  46.         if (Ecnt == 1) return 1;
  47.         for (int i = 0; i < n; i++) {
  48.             int num = a[i];
  49.             // Remove a[i]'s factors
  50.             for (int p : fac[num]) {
  51.                 map.put(p, map.get(p) - 1);
  52.                 if (map.get(p)==0) map.remove(p);
  53.             }
  54.             int found = 0;
  55.             for (int p : fac[num+1]) {
  56.                 if (map.containsKey(p)) {
  57.                     found=1;
  58.                     break;
  59.                 }
  60.             }
  61.             if (found==1) return 1; // 1 ops is suff
  62.             // Restore a[i]'s factors
  63.             for (int p : fac[num])
  64.                 map.put(p, map.getOrDefault(p, 0) + 1);
  65.         }
  66.  
  67.         // Nothing works → need 2 ops
  68.         return 2;
  69.     }
  70.  
  71.     static int gcd(int a, int b) {
  72.         while (b != 0) {
  73.             int t = b;
  74.             b = a % b;
  75.             a = t;
  76.         }
  77.         return a;
  78.     }
  79. }
  80.  
Success #stdin #stdout 0.72s 115204KB
comments (?)
stdin 
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 
2
0
2
1
1
1
https://ideone.com/rAa71Z
language:
Java (HotSpot 12)
created:
8 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!