fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7.     static HashMap<Integer,Integer> map=new HashMap<>();
  8.  
  9. 	public static void main (String[] args) throws java.lang.Exception
  10. 	{
  11. 		Scanner sc=new Scanner(System.in);
  12. 		int t=sc.nextInt();
  13. 		while(t-->0){
  14. 		    int n=sc.nextInt();
  15. 		    int [] a=new int[n];
  16. 		    int [] b=new int[n]; 
  17.  
  18. 		    for(int i=0;i<n;i++){
  19. 		        a[i]=sc.nextInt();
  20. 		    }
  21. 		    for(int i=0;i<n;i++){
  22. 		        b[i]=sc.nextInt();
  23. 		    }
  24. 		    int ans=solve(a,b);
  25. 		    System.out.println(ans);
  26. 		}
  27. 		sc.close();
  28. 	}
  29.  
  30. 	public static int solve(int []a, int []b){
  31. 	    int n=a.length;
  32. 	    int maxGCD=1;
  33.  
  34. 	    for(int i=0;i<n-1;i++){
  35. 	        for(int j=i+1;j<n;j++){
  36. 	            int g=gcd(a[i],a[j]);
  37. 	            maxGCD=Math.max(maxGCD,g);
  38. 	        }
  39. 	    }
  40. 	    if(maxGCD>1) return 0; 
  41.  
  42.  
  43. 	    int Ecnt=0;
  44. 	    map.clear();
  45. 	    for(int num : a){
  46. 	        addFactors(num);
  47. 	        if(num%2==0) Ecnt++;
  48. 	    }
  49. 	    if(Ecnt>=1) return 1; 
  50.  
  51.  
  52. 	    for(int i=0;i<n;i++){
  53. 	        removeFactors(a[i]); 
  54. 	        if(cFactor(a[i]+1)) return 1;
  55. 	        addFactors(a[i]); 
  56. 	    }
  57.  
  58. 	    return 2; 
  59. 	}
  60.  
  61. 	public static int gcd(int a, int b) {
  62.         while (b != 0) {
  63.             int temp = b;
  64.             b = a % b;
  65.             a = temp;
  66.         }
  67.         return Math.abs(a);
  68.     }
  69.  
  70.     public static void addFactors(int n) {
  71.         for (int i = 2; i * i <= n; i++) {
  72.             if (n % i == 0) {
  73.                 map.put(i, map.getOrDefault(i, 0) + 1);
  74.                 if(i != n/i) map.put(n/i, map.getOrDefault(n/i, 0) + 1);
  75.             }
  76.         }
  77.         map.put(n, map.getOrDefault(n, 0)+1);
  78.     }
  79.  
  80.     public static void removeFactors(int n){
  81.         for (int i = 2; i * i <= n; i++) {
  82.             if (n % i == 0) {
  83.                 map.put(i, map.get(i)-1);
  84.                 if(map.get(i)==0) map.remove(i);
  85.                 if(i != n/i){
  86.                     map.put(n/i, map.get(n/i)-1);
  87.                     if(map.get(n/i)==0) map.remove(n/i);
  88.                 }
  89.             }
  90.         }
  91.         map.put(n, map.get(n)-1);
  92.         if(map.get(n)==0) map.remove(n);
  93.     }
  94.  
  95.     public static boolean cFactor(int n){
  96.         for(int i=2;i*i<=n;i++){
  97.             if(n%i==0){
  98.                 if(map.containsKey(i)) return true;
  99.                 if(i!=n/i && map.containsKey(n/i)) return true;
  100.             }
  101.         }
  102.         return map.containsKey(n);
  103.     }
  104. }
  105.  
Success #stdin #stdout 0.16s 56664KB
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/C84hOl
language:
Java (HotSpot 12)
created:
6 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!