倍数，艾氏筛法思想

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <cstdlib>
 6 #include <cmath>
 7 #include <set>
 8 #include <map>
 9 #include <vector>
10 using namespace std;
11 
12 const int MAX = 1e6 + 10;
13 int res[MAX], a[MAX];
14 struct data{
15     int x, y;
16 }num[MAX];
17 int main()
18 {
19     int n, m, i, j, t = 1;
20     scanf("%d%d", &n, &m);
21     for(i = 0; i <= m; i++)
22     {
23         num[i].x = 0;
24         num[i].y = 0;
25     }
26     for(i = 0; i < n; i++)
27     {
28         scanf("%d", a + i);
29         if(a[i] <= m)
30         {
31             num[a[i]].x++;
32             num[a[i]].y++;
33         }
34     }
35     if(m > 1)
36     {
37         for(i = 2; i <= m; i++)
38         {
39             if(num[i].x > 0)
40             { 
41                 if(num[i].y > num[t].y)
42                         t = i;
43                 for(j = i * 2; j <= m; j += i)
44                 {
45                     num[j].y += num[i].x;
46                     if(num[j].y > num[t].y)
47                         t = j;
48                 }
49             }
50         }
51     }
52     j = 0;
53     for(i = 0; i < n; i++)
54     {
55         if(a[i] <= m && t % a[i] == 0)
56             res[j++] = i;
57     }    
58     printf("%d %d
", t, j);
59     for(i = 0; i < j; i++)
60     {
61         if(i != j - 1)
62             printf("%d ", res[i] + 1);
63         else
64             printf("%d", res[i] + 1);
65     }
66     printf("
");
67     return 0;
68 }