Advertisement
leoanjos

AAAAAAAAAAAAAAAAAA

Sep 24th, 2021
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define long long long int
  6.  
  7. vector<int> vis, dist;
  8. vector<vector<int>> cycles;
  9.  
  10. vector<pair<int, long>> operator *(vector<pair<int, long>> &a, vector<pair<int, long>> &b) {
  11.     int n = a.size();
  12.     vector<pair<int, long>> ans(n);
  13.  
  14.     for (int i = 0; i < n; i++)
  15.         ans[i] = make_pair(a[b[i].first].first, b[i].second + a[b[i].first].second);
  16.  
  17.     return ans;
  18. }
  19.  
  20. vector<pair<int, long>> exp(vector<pair<int, long>> &v, int k) {
  21.     if (k == 1) return v;
  22.  
  23.     vector<pair<int, long>> ans = exp(v, k >> 1);
  24.     ans = ans * ans;
  25.  
  26.     if (k & 1)
  27.         ans = ans * v;
  28.    
  29.     return ans;
  30. }
  31.  
  32. void get_cycle(vector<pair<int, long>> &nxt, int v) {
  33.     vector<int> cycle;
  34.     cycle.push_back(v);
  35.  
  36.     int u = nxt[v].first;
  37.     while (u != v) {
  38.         cycle.push_back(u);
  39.         u = nxt[u].first;
  40.     }
  41.  
  42.     cycles.push_back(cycle);
  43. }
  44.  
  45. void get_cycles(vector<pair<int, long>> &nxt, int v) {
  46.     if (vis[v] == 1) get_cycle(nxt, v);
  47.     else if (!vis[v]) {
  48.         vis[v]++;
  49.         get_cycles(nxt, nxt[v].first);
  50.         vis[v]++;
  51.     }
  52. }
  53.  
  54. void get_dist(vector<pair<int, long>> &nxt, int v) {
  55.     if (dist[v]) return;
  56.  
  57.     get_dist(nxt, nxt[v].first);
  58.     dist[v] = dist[nxt[v].first] + 1;
  59. }
  60.  
  61. int main() {
  62.     ios_base::sync_with_stdio(false);
  63.     cin.tie(NULL);
  64.  
  65.     int N, K;
  66.     cin >> N >> K;
  67.  
  68.     vector<int> divs(N + 1, 0);
  69.     for (int i = 1; i <= N; i++)
  70.         for (int j = i; j <= N; j += i)
  71.             divs[j]++;
  72.  
  73.     vector<pair<int, long>> nxt(N);
  74.     for (int i = 0; i < N; i++)
  75.         nxt[i] = make_pair((i + divs[i]) % N, i);
  76.  
  77.     vector<pair<int, long>> to = exp(nxt, K);
  78.  
  79.     vis.assign(N, 0);
  80.     for (int i = 0; i < N; i++)
  81.         if (!vis[i]) get_cycles(nxt, i);
  82.  
  83.     dist.assign(N, 0);
  84.     for (auto cycle: cycles)
  85.         for (auto v: cycle)
  86.             dist[v] = cycle.size();
  87.  
  88.     for (int i = 0; i < N; i++)
  89.         if (!dist[i]) get_dist(nxt, i);
  90.  
  91.     int start = -1;
  92.     long cost = LLONG_MAX;
  93.  
  94.     for (int i = 0; i < N && start == -1; i++)
  95.         if (dist[i] >= K && to[i].second < cost)
  96.             start = i;
  97.  
  98.     if (start == -1) cout << "-1\n";
  99.     else {
  100.         int ans = start;
  101.         for (int i = 0; i < K; i++) {
  102.             if (i) cout << " ";
  103.             cout << ans;
  104.             ans = nxt[ans].first;
  105.         }
  106.  
  107.         cout << "\n";
  108.     }
  109. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement