fork download
copy 
  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.  
  35.         // cumulative gcd 
  36.         int g = a[0];
  37.         for (int i = 1; i < n; i++) {
  38.             g = gcd(g, a[i]);
  39.             if (g > 1) return 0; // no ops needed
  40.         }
  41.  
  42.         HashMap<Integer, Integer> map = new HashMap<>();
  43.         int Ecnt = 0;
  44.  
  45.         for (int num : a) {
  46.             if ((num & 1) == 0) Ecnt++;
  47.             for (int p : fac[num])
  48.                 map.put(p, map.getOrDefault(p, 0) + 1);
  49.         }
  50.  
  51.         if (Ecnt == 1) return 1;
  52.  
  53.         for (int i = 0; i < n; i++) {
  54.             int num = a[i];
  55.  
  56.             // Remove a[i]'s factors
  57.             for (int p : fac[num]) {
  58.                 map.put(p, map.get(p) - 1);
  59.                 if (map.get(p)==0) map.remove(p);
  60.             }
  61.  
  62.             int found = 0;
  63.             for (int p : fac[num+1]) {
  64.                 if (map.containsKey(p)) {
  65.                     found=1;
  66.                     break;
  67.                 }
  68.             }
  69.             if (found==1) return 1; // 1 ops is sufficiant
  70.  
  71.             // Restore a[i]'s factors
  72.             for (int p : fac[num])
  73.                 map.put(p, map.getOrDefault(p, 0) + 1);
  74.         }
  75.  
  76.         // Nothing works → need 2 ops
  77.         return 2;
  78.     }
  79.  
  80.     static int gcd(int a, int b) {
  81.         while (b != 0) {
  82.             int t = b;
  83.             b = a % b;
  84.             a = t;
  85.         }
  86.         return a;
  87.     }
  88. }
  89.  
Success #stdin #stdout 0.89s 113020KB
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/c7bvn1
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!