SHARE
TWEET

Untitled

a guest Mar 1st, 2016 132 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.ArrayList;
  3. import java.util.StringTokenizer;
  4.  
  5. public class LcmSubsequenceJava implements Runnable {
  6.  
  7.     void solve() throws IOException {
  8.         int n = readInt();
  9.         int m = readInt();
  10.         int max = (int) 1e6;
  11.  
  12.         int[] input = readIntArray(n);
  13.         int[] count = new int[max + 1];
  14.         for (int x : input) {
  15.             if (x <= m) {
  16.                 count[x]++;
  17.             }
  18.         }
  19.  
  20.         int[] answer = new int[m + 1];
  21.         for (int i = 1; i <= max; i++) {
  22.             for (int j = i; j <= m; j += i) {
  23.                 answer[j] += count[i];
  24.             }
  25.         }
  26.         int maxAnswer = 0;
  27.         int lcm = 1;
  28.         for (int i = 1; i <= m; i++) {
  29.             if (answer[i] > maxAnswer) {
  30.                 maxAnswer = answer[i];
  31.                 lcm = i;
  32.             }
  33.         }
  34.         ArrayList<Integer> result = new ArrayList<>();
  35.         for (int i = 0; i < n; i++) {
  36.             if (lcm % input[i] == 0) result.add(i + 1);
  37.         }
  38.         out.println(lcm + " " + result.size());
  39.         for (int x : result) out.print(x + " ");
  40.         out.println();
  41.     }
  42.  
  43.     /*IO*/
  44.  
  45.     private BufferedReader in;
  46.     private PrintWriter out;
  47.     private StringTokenizer tok = new StringTokenizer("");
  48.  
  49.     void init() throws FileNotFoundException {
  50.         in = new BufferedReader(new InputStreamReader(System.in));
  51.         out = new PrintWriter(System.out);
  52.     }
  53.  
  54.     String readString() throws IOException {
  55.         while (!tok.hasMoreTokens()) {
  56.             try {
  57.                 tok = new StringTokenizer(in.readLine());
  58.             } catch (Exception e) {
  59.                 return null;
  60.             }
  61.         }
  62.         return tok.nextToken();
  63.     }
  64.  
  65.     int readInt() throws IOException {
  66.         return Integer.parseInt(readString());
  67.     }
  68.  
  69.     int[] readIntArray(int size) throws IOException {
  70.         int[] res = new int[size];
  71.         for (int i = 0; i < size; i++) {
  72.             res[i] = readInt();
  73.         }
  74.         return res;
  75.     }
  76.  
  77.     public static void main(String[] args) {
  78.         new LcmSubsequenceJava().run();
  79.     }
  80.  
  81.     public void run() {
  82.         try {
  83.             init();
  84.             solve();
  85.             out.close();
  86.         } catch (Exception e) {
  87.             e.printStackTrace();
  88.             System.exit(-1);
  89.         }
  90.     }
  91.  
  92. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top