fork download
copy 
  1. //NiceDuck
  2. #include "bits/stdc++.h"
  3. typedef long long ll;
  4. using namespace std;
  5. #define FILE "000"
  6. #define foru(i,a,b) for(int i=(int)(a); i<=(int)(b); ++i)
  7. #define ford(i,a,b) for(int i=(int)(a); i>=(int)(b); --i)
  8. #define fastio ios_base::sync_with_stdio(0);cin.tie(0);
  9. #define pb push_back
  10. #define fi first
  11. #define se second
  12. #define pii pair<int,int>
  13. #define pil pair<int,ll>
  14. #define pli pair<ll,int>
  15. #define MOD 1000000007
  16. #define el "\n"
  17.  
  18. const int MAX=3e5+5;
  19. int t,n,a[MAX],f[MAX];
  20. vector<pii> g[MAX];
  21. void pre()
  22. {
  23.     foru(i,1,3e5)
  24.     {
  25.         for(int j=1; 1LL*j*j<=i; ++j)
  26.         {
  27.             if(i%j==0) g[i].pb(make_pair(j,i/j));
  28.         }
  29.     }
  30. }
  31. void calc()
  32. {
  33.     foru(i,1,n) f[i]=1e9;
  34.     foru(i,1,n) f[a[i]]=1;
  35.     foru(i,1,n)
  36.     {
  37.         if(f[i]==1) 
  38.         {
  39.             cout<<"1 ";
  40.             continue;
  41.         }
  42.         for(pii p:g[i])
  43.         {
  44.             f[i]=min(f[i],f[p.fi]+f[p.se]);
  45.         }
  46.         cout<<(f[i]==1e9 ? -1 : f[i])<<' ';
  47.     }
  48.     cout<<el;
  49. }
  50.  
  51. int main()
  52. {
  53.     fastio
  54.     #ifndef ONLINE_JUDGE
  55.     freopen(FILE ".inp","r",stdin);
  56.     freopen(FILE ".out","w",stdout);
  57.     #endif // ONLINE_JUDGE
  58.  
  59.     pre();
  60.     cin>>t;
  61.     while(t--)
  62.     {
  63.         cin>>n; foru(i,1,n) cin>>a[i];
  64.         calc();
  65.     }
  66.  
  67.     return 0;
  68. }
Success #stdin #stdout 0.49s 34740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FOTRv8
language:
C++14 (gcc 8.3)
created:
14 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!