Guest User

1419E

a guest
Sep 19th, 2020
2,234
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool prime(int x) {
  5.     if (x == 2 || x == 3) return true;
  6.     for (int i = 2; i * i <= x; ++i) {
  7.         if (x % i == 0) return false;
  8.     }
  9.     return true;
  10. }
  11.  
  12. signed main() {
  13.     int T;
  14.     cin >> T;
  15.     while (T --> 0) {
  16.         int n;
  17.         cin >> n;
  18.         vector<int> d;
  19.         for (int i = 2; i * i <= n; ++i) {
  20.             if (n % i == 0) {
  21.                 d.emplace_back(i);
  22.                 d.emplace_back(n / i);
  23.             }
  24.         }
  25.         d.emplace_back(n);
  26.         sort(d.begin(), d.end());
  27.         d.resize(unique(d.begin(), d.end()) - d.begin());
  28.  
  29.         if (d.size() == 3 && prime(d[0]) && prime(d[1])) {
  30.             for (auto x : d) cout << x << ' ';
  31.             cout << '\n' << 1 << '\n';
  32.             continue;
  33.         }
  34.  
  35.         unordered_map<int, bool> used;
  36.         vector<int> primes;
  37.         for (int i = 2; i * i <= n; ++i) {
  38.             if (n % i == 0) {
  39.                 primes.emplace_back(i);
  40.                 while (n % i == 0) n /= i;
  41.             }
  42.         }
  43.         if (n > 1) primes.emplace_back(n);
  44.  
  45.         vector<int> connect(primes.size());
  46.         for (int i = 0; i < (int)primes.size(); ++i) {
  47.             int p = primes[i], q = primes[(i + 1) % primes.size()];
  48.             for (int j = 0; j < (int)d.size(); ++j) {
  49.                 if (!used[d[j]] && d[j] % p == 0 && d[j] % q == 0) {
  50.                     used[d[j]] = true;
  51.                     connect[i] = d[j];
  52.                     break;
  53.                 }
  54.             }
  55.         }
  56.  
  57.         for (int i = 0; i < (int)primes.size(); ++i) {
  58.             int p = primes[i];
  59.             used[p] = true;
  60.             cout << p << ' ';
  61.             for (int j = 0; j < (int)d.size(); ++j) {
  62.                 if (!used[d[j]] && d[j] % p == 0) {
  63.                     used[d[j]] = true;
  64.                     cout << d[j] << ' ';
  65.                 }
  66.             }
  67.             if (primes.size() > 1) {
  68.                 cout << connect[i] << ' ';
  69.             }
  70.         }
  71.         cout << '\n' << 0 << '\n';
  72.     }
  73.     return 0;
  74. }
RAW Paste Data