Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.ArrayList;
- import java.util.StringTokenizer;
- public class LcmSubsequenceJava implements Runnable {
- void solve() throws IOException {
- int n = readInt();
- int m = readInt();
- int max = (int) 1e6;
- int[] input = readIntArray(n);
- int[] count = new int[max + 1];
- for (int x : input) {
- if (x <= m) {
- count[x]++;
- }
- }
- int[] answer = new int[m + 1];
- for (int i = 1; i <= max; i++) {
- for (int j = i; j <= m; j += i) {
- answer[j] += count[i];
- }
- }
- int maxAnswer = 0;
- int lcm = 1;
- for (int i = 1; i <= m; i++) {
- if (answer[i] > maxAnswer) {
- maxAnswer = answer[i];
- lcm = i;
- }
- }
- ArrayList<Integer> result = new ArrayList<>();
- for (int i = 0; i < n; i++) {
- if (lcm % input[i] == 0) result.add(i + 1);
- }
- out.println(lcm + " " + result.size());
- for (int x : result) out.print(x + " ");
- out.println();
- }
- /*IO*/
- private BufferedReader in;
- private PrintWriter out;
- private StringTokenizer tok = new StringTokenizer("");
- void init() throws FileNotFoundException {
- in = new BufferedReader(new InputStreamReader(System.in));
- out = new PrintWriter(System.out);
- }
- String readString() throws IOException {
- while (!tok.hasMoreTokens()) {
- try {
- tok = new StringTokenizer(in.readLine());
- } catch (Exception e) {
- return null;
- }
- }
- return tok.nextToken();
- }
- int readInt() throws IOException {
- return Integer.parseInt(readString());
- }
- int[] readIntArray(int size) throws IOException {
- int[] res = new int[size];
- for (int i = 0; i < size; i++) {
- res[i] = readInt();
- }
- return res;
- }
- public static void main(String[] args) {
- new LcmSubsequenceJava().run();
- }
- public void run() {
- try {
- init();
- solve();
- out.close();
- } catch (Exception e) {
- e.printStackTrace();
- System.exit(-1);
- }
- }
- }
Add Comment
Please, Sign In to add comment