fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10.     public List<Integer> factors(int n, Map<Integer, Integer> mp) {
  11.         List<Integer> factors = new ArrayList<Integer>();
  12.         for (int i=1;i*i<=n;i++) {
  13.             if (n%i==0) {
  14.                 factors.add(i);
  15.                 mp.put(i, mp.getOrDefault(i, 0) + 1);
  16.                 if (i!=n/i) {
  17.                     factors.add(n/i);
  18.                     mp.put(n/i, mp.getOrDefault(n/i, 0) + 1);
  19.                 }
  20.             }
  21.         }
  22.         return factors;
  23.     }
  24.     public List<Integer> factors(int n) {
  25.         List<Integer> result = new ArrayList<>();
  26.         for (int i=1;i*i<n;i++) {
  27.             if (n%i==0) {
  28.                 result.add(i);
  29.                 if (i!=n/i) {
  30.                     result.add(n/i);
  31.                 }
  32.             }
  33.         }
  34.         return result;
  35.     }
  36.     public int countPairInArrayWithGivenGCD(int[] arr, int gcdValue) {
  37.         Map<Integer, Integer> mp = new HashMap<>();
  38.         Arrays.sort(arr);
  39.         int maxVal=0;
  40.         for (int i=0;i<arr.length;i++) {
  41.             factors(arr[i], mp);
  42.             maxVal = Math.max(maxVal, arr[i]);
  43.         }
  44.         int[] gcd = new int[maxVal+1];
  45.         Arrays.fill(gcd, 0);
  46.         for (int i=arr.length-1;i>=0;i--) {
  47.             int value = mp.get(arr[i]);
  48.             int countPair = (value * (value - 1)) / 2;
  49.             int sum = 0;
  50.             for (int j=arr[i];j<=arr[arr.length-1];j=j+arr[i]) {
  51.                 sum = sum + gcd[j];
  52.             }
  53.             gcd[arr[i]] = countPair - sum;
  54.         }
  55.         return gcd[gcdValue];
  56.     }
  57.     public static void main(String[] args) {
  58.         Ideone practice = new Ideone();
  59.         int count =  practice.countPairInArrayWithGivenGCD(new int[]{1, 2, 4, 6, 8, 10, 11}, 2);
  60.         System.out.println("The count of pair having gcd value " + 2 + " is " + count);
  61.     }
  62. }
Success #stdin #stdout 0.12s 55760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The count of pair having gcd value 2 is 9
https://ideone.com/xb7j8t
language:
Java (HotSpot 12)
created:
18 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!