fork(1) download 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Codechef
  6. {
  7.     static int MAX_N=200000;
  8.     static ArrayList<Integer>[]U=new ArrayList[MAX_N+5]; 
  9.     static void div(){
  10.         for (int i=1;i<=MAX_N;i++){
  11.             U[i]=new ArrayList<>();
  12.         }
  13.         for (int i=1;i<=MAX_N;i++){
  14.             for (int j=i;j<=MAX_N;j+=i){
  15.                 U[j].add(i);
  16.             }
  17.         }
  18.     }
  19.     public static void main (String[] args) throws java.lang.Exception
  20.     {
  21.         // your code goes here
  22.         div();
  23.         Scanner sc=new Scanner(System.in);
  24.         int t=sc.nextInt();
  25.         while(t-->0){
  26.             int n=sc.nextInt();
  27.             int y=sc.nextInt();
  28.             int[]arr=new int[n];
  29.             for (int i=0;i<n;i++){
  30.                 arr[i]=sc.nextInt();
  31.             }
  32.             // gcd == y
  33.             int gcd = gcdy(arr,y);
  34.             System.out.println(gcd);
  35.         }
  36.         sc.close();
  37.     }
  38.     public static int gcdy(int[]arr,int y){
  39.         int max =0;
  40.         for(int num:arr){
  41.             max=Math.max(max,num);
  42.         }
  43.         int[]freq=new int[max+1];
  44.         for(int num:arr){
  45.             freq[num]++;
  46.         }
  47.         int[]u=new int[max+1];
  48.         for(int i=1;i<=max;i++){
  49.             for(int j=i;j<= max;j+=i){
  50.                 u[i]+=freq[j];
  51.             }
  52.         }
  53.         int[]mul=new int[max + 1];
  54.         int[]g=new int[max + 1];
  55.         for(int i=1;i<=max;i++){
  56.             if(u[i]>=2){
  57.                 mul[i]=u[i]*(u[i]-1)/2;  //nC2 : ways to get all no. of pairs
  58.             }
  59.         }
  60.         g[max]=mul[max];
  61.         for(int i=max-1;i>=1;i--){
  62.             int multiple=0;
  63.             for(int j=2*i;j<=max;j+=i){
  64.                 multiple+=g[j];
  65.             }
  66.             g[i]=mul[i]-multiple;
  67.         }
  68.         return g[y];
  69.     }
  70. }
Success #stdin #stdout 0.42s 114748KB
comments (?)
stdin 
1
5 2
2 4 6 8 10
stdout 
9
https://ideone.com/Le974z
language:
Java (HotSpot 12)
created:
1 day 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!