fork download
copy 
  1. import java.util.*;
  2.  class Ideone 
  3. {
  4.     static int maxn=5000+1;
  5.     static int gcd(int a,int b)
  6.     {
  7.         while(b!=0)
  8.         {
  9.             int temp=a%b;
  10.             a=b;
  11.             b=temp;
  12.         }
  13.         return a;
  14.     }
  15.  
  16.  
  17.     public static void main(String[] args) 
  18.     {
  19.         Scanner sc=new Scanner(System.in);
  20.         int t=sc.nextInt();
  21.         while(t-->0)
  22.         {
  23.             int n=sc.nextInt();
  24.             int arr[]=new int[n];
  25.             for(int i=0;i<n;i++)
  26.             arr[i]=sc.nextInt();
  27.  
  28.            int g=0;
  29.            for(int i=0;i<n;i++)
  30.            g=gcd(g,arr[i]);
  31.  
  32.            int gcount=0;
  33.            for(int i=0;i<n;i++)
  34.            {
  35.              if(arr[i]==g)
  36.              gcount++;
  37.            }
  38.  
  39.            if(gcount>0)
  40.            System.out.println(n-gcount);
  41.  
  42.            else
  43.            {
  44.  
  45.             Queue<Integer> q=new LinkedList<>();
  46.             boolean visited[]=new boolean[maxn];
  47.             int dp[]=new int[maxn];
  48.  
  49.             for(int i=0;i<n;i++)
  50.             {
  51.                 q.add(arr[i]);
  52.                 visited[arr[i]]=true;
  53.                 dp[arr[i]]=0;
  54.             }
  55.  
  56.             while(!q.isEmpty())
  57.             {
  58.                 int temp=q.poll();
  59.                 for(int ele:arr)
  60.                 {
  61.  
  62.                         int val=gcd(temp,ele);
  63.                        if(!visited[val])
  64.                        {
  65.                           q.add(val);
  66.                           visited[val]=true;
  67.                           dp[val]=dp[temp]+1;
  68.                        }
  69.  
  70.  
  71.                 }
  72.             }
  73.  
  74.             System.out.println(n-1 +dp[g]);
  75.            }
  76.  
  77.  
  78.         }
  79.  
  80.  
  81.  
  82.     }
  83.  
  84. }
  85.  
Success #stdin #stdout 0.14s 54600KB
comments (?)
stdin
copy 
3
3
12 20 30
6
1 9 1 9 8 1
3
6 14 15
stdout
copy 
4
3
3
https://ideone.com/jI7SvL
language:
Java (HotSpot 12)
created:
5 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!