fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define vodichc2 ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define fr(i,a,b) for(long long i=a;i<=b;i++)
  6. #define frd(i,a,b) for(long long i=a;i>=b;i--)
  7. #define openfile if(fopen("Data.inp","r")) {freopen("Data.inp", "r", stdin); freopen("Data.out", "w", stdout);}
  8. ll n;
  9. ll a[200005],f[200005];
  10. map <ll,ll> m;
  11. void doc()
  12. {
  13. 	cin >> n;
  14. 	fr(i,1,n) cin >> a[i];
  15. }
  16. void xuly()
  17. {
  18. 	sort(a+1,a+n+1);
  19. 	fr(i,1,n) f[i]=1;
  20. 	fr(i,2,n)
  21. 	{
  22. 		fr(j,1,i-1)
  23. 		{
  24. 			if(a[i]%a[j]==0) f[i]=max(f[i],f[j]+1);
  25. 		}
  26. 	}
  27. 	ll cnt=*max_element(f+1,f+n+1);
  28. 	cout << n-cnt;
  29. }
  30. void sub2()
  31. {
  32. 	fr(i,1,n) m[a[i]]+=1;
  33. 	fr(i,1,2e5) f[i]=m[i];
  34. 	fr(i,1,2e5)
  35. 	{
  36. 		if(m[i]>0) 
  37. 		{
  38. 			for(ll j=2*i;j<=2e5;j+=i)
  39. 			{
  40. 				if(m[j]>0) f[j]=max(f[j],f[i]+m[j]);
  41. 			}
  42. 		}
  43. 	}
  44. 	ll cnt=*max_element(f+1,f+200005+1);
  45. 	cout << n-cnt;
  46. }
  47. signed main()
  48. {
  49. 	vodichc2
  50. 	openfile
  51. 	doc();
  52. 	sub2();
  53. }
  54.  
  55.  
  56.  
  57. /*
  58.  
  59.  
  60.                                                ¦¦¦¦¦¦¦¦¦¦¦¦
  61.                                              ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  62.                                            ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  63.                                          ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  64.                                          ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦¦¦
  65.                                      ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  66.                                ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  67.                                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  68.                                                      ¦¦¦¦¦¦¦¦¦¦¦¦
  69.                                                      ¦¦¦¦¦¦¦¦¦¦
  70.                                                    ¦¦¦¦¦¦  ¦¦¦¦
  71.                                                ¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  72.                                            ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  73.                                          ¦¦¦¦  ¦¦¦¦¦¦¦¦¦¦
  74.                                        ¦¦¦¦¦¦¦¦        ¦¦¦¦¦¦¦¦¦¦
  75.                                      ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  76.                                    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  77.                                    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦
  78.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦
  79.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦
  80.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦    ¦¦
  81.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦
  82.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦NGUYEN THANH PHONG¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  83.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦    ¦¦
  84.                                  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦LE KHIET¦¦¦¦¦¦¦¦¦¦¦¦¦    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦    ¦¦
  85.                                    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦  ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  86.                                    ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦            ¦¦  ¦¦¦¦¦¦
  87.                                        ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  88.                                          ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  89.                                            ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  90.                                                ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  91.                                                          ¦¦¦¦¦¦¦¦¦¦
  92.                                                          ¦¦¦¦¦¦¦¦¦¦
  93.                                                            ¦¦  ¦¦
  94.                                                            ¦¦  ¦¦
  95.                                                            ¦¦  ¦¦
  96.                                                            ¦¦  ¦¦
  97.                                                  ¦¦¦¦¦¦¦¦  ¦¦  ¦¦
  98.                                              ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦
  99. */
Success #stdin #stdout 0.09s 18292KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pI4UI0
language:
C++14 (gcc 8.3)
created:
148 days ago
visibility:
secret

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!