fork download 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Solution {
  5.     public static void main(String args[]) {
  6.         Scanner sc = new Scanner(System.in);
  7.  
  8.         int n = sc.nextInt();
  9.         int y = sc.nextInt();
  10.  
  11. 		int arr[] = new int[n];
  12.  
  13.         for (int i = 0; i < n; i++)
  14.             arr[i] = sc.nextInt();
  15. 		int max = Integer.MIN_VALUE;
  16.         for (int i = 0; i < n; i++)
  17.             max = Math.max(max, arr[i]);
  18.  
  19.  
  20.         int freq[] = new int[max + 1];
  21.         for (int v : arr)
  22.             freq[v]++;
  23.  
  24.         int u[] = new int[max + 1];
  25.         for (int i = 1; i <= max; i++) {
  26.             for (int j = i; j <= max; j += i) {
  27.                 u[i] += freq[j];
  28.             }
  29.         }
  30.  
  31.         int mul[] = new int[max + 1];
  32.         for (int i = 1; i <= max; i++) {
  33.  
  34.             mul[i] = u[i] * (u[i] - 1) / 2;
  35.         }
  36.  
  37.         int g[] = new int[max + 1];
  38.         for (int i = max; i >= 1; i--) {
  39.             g[i] = mul[i];
  40.             for (int j = 2 * i; j <= max; j += i) {
  41.  
  42.                 g[i] -= g[j];
  43.             }
  44.         }
  45. 		if (y <= 0 || y > max) {
  46.             System.out.println(0);
  47.         } else {
  48.             System.out.println(g[y]);
  49.         }
  50.     }
  51. }
  52.  
Success #stdin #stdout 0.17s 54552KB
comments (?)
stdin 
5 2
2 4 6 3 9
stdout 
3
https://ideone.com/E0Dbps
language:
Java (HotSpot 12)
created:
2 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!