fork download
copy 
  1. //#pragma GCC optimize("Ofast")
  2. //#pragma GCC target("avx,avx2,fma")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5. #define ll long long
  6. #define fi first
  7. #define se second
  8. #define MOD 1000000007
  9. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  10. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  11. #define ALL(x) (x).begin(),(x).end()
  12. #define ii pair<int,int>
  13. #define iii pair<int,pair<int,int>>
  14. //const int MOD = 998244853;
  15. const int MAXN = 2e5 + 7;
  16. const int maxn = 1e7 + 7;
  17. int a[MAXN],dp[MAXN],Try[MAXN],prime[maxn];
  18. void sieve(){
  19.     FOR(i,2,maxn - 1)if (!prime[i]){
  20.         prime[i] = i;
  21.         for (ll j = 1ll * i * i;j <= maxn;j+=i)prime[j] = i;
  22.     }
  23. }
  24. vector<int> bit[maxn];
  25. void update(int id,int x,int v){
  26.     int len = maxn / id;
  27.     for (;x <= len;x+=x&-x)bit[id][x] = max(bit[id][x],v);
  28. }
  29. int get(int id,int x){
  30.     int ans = 0;
  31.     for (;x;x-=x&-x)ans = max(ans,bit[id][x]);
  32.     return ans;
  33. }
  34. int main(){
  35.     ios_base::sync_with_stdio(false);
  36.     cin.tie(0); cout.tie(0);
  37.     //freopen("MAXRECT.inp","r",stdin);
  38.     //freopen("MAXRECT.out","w",stdout);
  39.     sieve();
  40.     int n,d;cin >> n >> d;
  41.     FOR(i,1,n)cin >> a[i];
  42.     FOR(i,1,n){
  43.         dp[i] = 1;
  44.         int t = a[i];
  45.         vector<int> v;
  46.         while(t > 1){
  47.             int p = prime[t];
  48.             while(t % p == 0)t = t / p;
  49.             v.push_back(p);
  50.         }
  51.         if (!d)v.push_back(1);
  52.         for (auto x : v)if (bit[x].empty())
  53.         FOR(j,0,maxn / x)bit[x].push_back(0);
  54.         for (auto x : v)dp[i] = max(dp[i],get(x,a[i] / x - 1) + 1);
  55.         for (auto x : v)update(x,a[i] / x,dp[i]);
  56.     }
  57.     int ans = 0,id;
  58.     FOR(i,1,n)if (ans < dp[i]){
  59.         ans = dp[i];
  60.         id = i;
  61.     }
  62.     vector<int> res;
  63.     res.push_back(id);
  64.     FOD(i,1,id - 1)if (a[i] < a[id] && dp[id] - 1 == dp[i] && __gcd(a[i],a[id]) > d){
  65.         res.push_back(i);
  66.         id = i;
  67.     }
  68.     reverse(ALL(res));
  69.     cout << ans << '\n';
  70.     for (auto x : res)cout << x << ' ';
  71.     return 0^0;
  72. }
Success #stdin #stdout 0.25s 325556KB
comments (?)
stdin
copy 
6 1
2 3 4 8 9 12
stdout
copy 
4
1 3 4 6
https://ideone.com/iRXy6T
language:
C++ (gcc 8.3)
created:
8 hours 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!