IQOverload

CF 256E

Aug 17th, 2014
283
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.44 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <deque>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <sstream>
  14. #include <stack>
  15. #include <string>
  16. #include <utility>
  17. #include <vector>
  18.  
  19. #define fst first
  20. #define snd second
  21. #define all(x) (x).begin(), (x).end()
  22. #define clr(a, v) memset(a, v, sizeof(a))
  23. #define pb push_back
  24. #define mp make_pair
  25. #define sz(x) (int)(x.size())
  26. #define FORN(i,s,n) for(int i=s;i<(int)(n);i++)
  27. #define FOR(i,n) FORN(i,0,n)
  28. #define FORIT(i,x) for( typeof x.begin()  i=x.begin(); i!=x.end(); i++ )
  29. #define trace(x)    cerr << #x << ": " << x << endl;
  30. #define trace2(x, y) cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  31.  
  32. using namespace std;
  33.  
  34. typedef long long int64;
  35. typedef vector <int> vi;
  36. typedef pair <int,int> ii;
  37. typedef vector <string> vs;
  38. typedef vector <ii> vii;
  39.      
  40. const int MAX = 100005;
  41.  
  42. int64 X, a[MAX+2], b[MAX+2];
  43. vector <int64> d;
  44. vector < vector <int64> > dd;
  45. map <int64,int> pos, fst, snd;
  46. int seg[MAX], cnt, sz_a;
  47.  
  48. void solve( int64 k ){
  49.  
  50.     if( k == 0 ){
  51.         sz_a = 1; a[0] = X; return ;
  52.     }
  53.  
  54.     else if( k % 2 ){
  55.         solve(k-1); cnt = 0;
  56.         FOR( i , sz_a ){
  57.             int64 t = pos[ a[i] ];
  58.             FOR( j , dd[t].size() ){
  59.                 b[cnt++] = dd[t][j];
  60.                 if( cnt >= MAX ) break;
  61.             }
  62.             if( cnt >= MAX ) break;
  63.         }
  64.         FOR( i , cnt ) a[i] = b[i];
  65.         sz_a = cnt; return ;
  66.     }
  67.  
  68.     solve( k/2 ); fst.clear(); snd.clear(); cnt = 0;
  69.     FOR( i ,  sz_a ){
  70.         if( !snd.count(a[i]) ) snd[ a[i] ] = i;
  71.     }
  72.     fst[1] = 0;
  73.     FORN( i , 1 , d.size() ) fst[ d[i] ] = snd[ d[i-1] ] + 1;
  74.     FOR( i , sz_a ){
  75.         int t = pos[a[i]];
  76.         FOR( j , dd[t].size() ){
  77.             int64 cur = dd[t][j];
  78.             FORN( l , fst[cur] , snd[cur]+1 ){
  79.                 b[cnt++] = a[l];
  80.                 if( cnt >= MAX ) break;
  81.             }
  82.             if( cnt >= MAX ) break;
  83.         }
  84.         if( cnt >= MAX ) break;
  85.     }  
  86.     FOR( i , cnt ) a[i] = b[i]; sz_a = cnt;
  87.     return ;
  88. }
  89.  
  90. int main() {
  91.  
  92.     int64 k;
  93.     cin >> X >> k;
  94.     for( int64 i = 1 ; i*i <= X ; i++ ){
  95.         if( i*i == X ) d.pb(i);
  96.         else if( X % i == 0 ) d.pb( i ), d.pb( X/i );
  97.     }
  98.     sort( all ( d ) );
  99.     vector <int64> aux;
  100.     FOR( i , d.size() ){
  101.         pos[ d[i] ] = i;
  102.         aux.clear();
  103.         FOR( j , d.size() ){
  104.             if( d[i] % d[j] == 0 ) aux.pb( d[j] );
  105.         }
  106.         dd.pb( aux );
  107.     }
  108.     solve( k );
  109.     sz_a = min( sz_a , 100000 );
  110.     FOR( i , sz_a ){
  111.         if( i ) printf(" ");
  112.         cout << a[i];
  113.     }
  114.     cout << endl;
  115.  
  116.     return 0;
  117. }
Advertisement
Add Comment
Please, Sign In to add comment