daily pastebin goal
47%
SHARE
TWEET

Untitled

a guest Jun 19th, 2018 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. long gcd(long a, long b) {
  4.         return b == 0 ? a : gcd(b, a % b);
  5. }
  6.  
  7. long calcLCM(long a, long b) {
  8.     return a * b / gcd(a,b);
  9. }
  10.  
  11. int main() {
  12.     int n, *perm, *used;
  13.     std::cin >> n;
  14.     perm = new int[n];
  15.     used = new int[n];
  16.     long lcm = 1;
  17.     for(int i = 0; i < n; i ++) {
  18.         std::cin >> perm[i];
  19.         perm[i]--;
  20.         used[i] = 0;
  21.     }
  22.     int high = 0;
  23.     while(high < n) {
  24.         int curr = high; bool first = true;
  25.         int clen = 0;
  26.         while(first || curr != high) {
  27.             first = false;
  28.             used[curr] = 1;
  29.             curr = perm[curr];
  30.             clen ++;
  31.         }
  32.         lcm = calcLCM(lcm, clen);
  33.         while(high < n && used[high] == 1) high++;
  34.     }
  35.     std::cout << lcm;
  36.     delete[] perm;
  37.     delete[] used;
  38.     return 0;
  39. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top