Advertisement
Guest User

Untitled

a guest
Jan 11th, 2023
3,079
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.43 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 300100;
  5. const int kMaxA = 300100;
  6. const int oo = 1e9;
  7. vector<int> edges[kMaxA];
  8. int dist[kMaxA], prv[kMaxA];
  9. bool used[kMaxA];
  10. int prv_id[kMaxA];
  11. int min_prime[kMaxA];
  12. int n, a[N];
  13. int boss[kMaxA];
  14. int mem_id[kMaxA];
  15. int source, dest;
  16.  
  17. int main() {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(nullptr);
  20.  
  21.     cin >> n;
  22.     for (int i = 0; i < n; i++) {
  23.         cin >> a[i];
  24.         mem_id[a[i]] = i;
  25.     }
  26.     cin >> source >> dest;
  27.     source--; dest--;
  28.  
  29.     if (a[source] == a[dest]) {
  30.         if (source == dest) {
  31.             cout << "1\n" << source + 1 << '\n';
  32.         } else if (a[source] == 1) {
  33.             cout << -1;
  34.         } else {
  35.             cout << "2\n" << source + 1 << " " << dest + 1;
  36.         }
  37.         return 0;
  38.     }
  39.  
  40.     fill(min_prime, min_prime + kMaxA, oo);
  41.  
  42.     for (int prime = 2; prime < kMaxA; prime++) {
  43.         if (min_prime[prime] != oo) {
  44.             continue;
  45.         }
  46.         min_prime[prime] = prime;
  47.  
  48.         if (ll(prime) * ll(prime) >= kMaxA) {
  49.             continue;
  50.         }
  51.  
  52.         for (int value = prime * prime; value < kMaxA; value += prime) {
  53.             min_prime[value] = min(min_prime[value], prime);
  54.         }
  55.     }
  56.  
  57.     fill(boss, boss + kMaxA, -1);
  58.  
  59.     fill(dist, dist + kMaxA, oo);
  60.     fill(prv, prv + kMaxA, -1);
  61.     queue<int> pr_queue;
  62.  
  63.     for (int i = 0; i < n; i++) {
  64.         bool is_need = edges[a[i]].empty();
  65.  
  66.         int value = a[i];
  67.         int pre_prime = -1;
  68.         while (value > 1) {
  69.             int cur_prime = min_prime[value];
  70.             if (cur_prime != pre_prime && is_need) {
  71.                 edges[a[i]].push_back(cur_prime);
  72.             }
  73.  
  74.             if (cur_prime != pre_prime && i == source) {
  75.                 dist[cur_prime] = 0;
  76.                 pr_queue.push(cur_prime);
  77.             }
  78.  
  79.             pre_prime = cur_prime;
  80.             boss[cur_prime] = i;
  81.             value /= cur_prime;
  82.         }
  83.     }
  84.  
  85.     fill(used, used + kMaxA, false);
  86.  
  87.     while (!pr_queue.empty()) {
  88.         int cur_prime = pr_queue.front();
  89.         pr_queue.pop();
  90.  
  91.         for (int value = cur_prime * 2; value < kMaxA; value += cur_prime) {
  92.             if (used[value]) {
  93.                 continue;
  94.             }
  95.             used[value] = true;
  96.  
  97.             for (int next_prime : edges[value]) {
  98.                 if (dist[next_prime] == oo) {
  99.                     dist[next_prime] = dist[cur_prime] + 1;
  100.                     prv_id[next_prime] = mem_id[value];
  101.                     prv[next_prime] = cur_prime;
  102.                     pr_queue.push(next_prime);
  103.                 }
  104.             }
  105.         }
  106.     }
  107.  
  108.     int best_dist = oo;
  109.     int best_prime = -1;
  110.  
  111.     for (int prime : edges[a[dest]]) {
  112.         if (dist[prime] < best_dist) {
  113.             best_dist = dist[prime];
  114.             best_prime = prime;
  115.         }
  116.     }
  117.  
  118.     if (best_dist == oo) {
  119.         cout << -1;
  120.         return 0;
  121.     }
  122.  
  123.     vector<int> route;
  124.  
  125.     int cur_prime = best_prime;
  126.     route.push_back(dest);
  127.     route.push_back(prv_id[best_prime]);
  128.     while (prv[cur_prime] != -1) {
  129.         cur_prime = prv[cur_prime];
  130.         route.push_back(prv_id[cur_prime]);
  131.     }
  132.  
  133.     std::reverse(route.begin(), route.end());
  134.     route.front() = source;
  135.  
  136.     cout << route.size() << '\n';
  137.     for (int id : route) {
  138.         cout << id + 1 << " ";
  139.     }
  140.  
  141.     return 0;
  142. }
  143.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement