fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define dd double
  5. #define ld long double
  6. #define ull unsigned long long
  7. #define yes cout << "YES\n"
  8. #define no cout << "NO\n"
  9. #define el "\n"
  10. #define Arwa ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  11. #define fix(x) cout << fixed << setprecision(x)
  12. #define all(v) v.begin(),v.end()
  13. #define dpp(v,val) memset(v,val,sizeof(v))
  14. #define mod 1e9+7
  15. #define oo 1e9
  16. const int N = 1e5 + 5;
  17. map<int,int>pf(int n)
  18. {
  19.   map<int,int>mp;
  20.   for(int i=2;i<=n*n;i++)
  21.   {
  22.      if((n%i==0))
  23.      {
  24.      while(n%i==0) n/=i;
  25.      mp[i]=1;
  26.      }
  27.   }
  28.   if(n>1) mp[n]=1;
  29.   return mp;
  30. }
  31. void HereWeGoAgain()
  32. {
  33.   int n;
  34.   cin>>n;
  35.   vector<int>v(n);
  36.   for(int i=0;i<n;i++)
  37.   cin>>v[i];
  38.   int dp[N]={};
  39.   if(n==1) {cout<<1<<el; return ;}
  40.   for(auto it:v)
  41.   {
  42.     if(it!=1)
  43.     {
  44.     auto pf1=pf(it);
  45.     int mx=0;
  46.     for(auto it1:pf1)
  47.     { dp[it1.first]++;mx=max(dp[it1.first],mx); }
  48.     for(auto it1:pf1)
  49.     dp[it1.first]=mx;
  50.     }
  51.   }
  52.   int ans=0;
  53.   for(int i=1;i<=n;i++) ans=max(dp[i],ans); cout<<ans<<el;
  54. }
  55. int32_t main() 
  56. {
  57.     Arwa
  58.     int t=1;
  59.     //cin>>t;
  60.     for(int i=1;i<=t;i++)
  61.     {
  62.     HereWeGoAgain();
  63.     }
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/DlElPp
language:
C++ (gcc 8.3)
created:
3 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!