poj 2369 Permutations 置换

题目链接

给一个数列， 求这个数列置换成1， 2， 3....n需要多少次。

就是里面所有小的置换的长度的lcm。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

int a[], vis[];

int gcd(int x, int y) {

    return y?gcd(y, x%y):x;

}

int lcm(int x, int y) {

    return x/gcd(x, y)*y;

}

int main()

{

    int n;

    while(cin>>n) {

        for(int i = ; i<n; i++){

            scanf("%d", &a[i]);

            a[i]--;

        }

        int ans = ;

        for(int i = ; i<n; i++) {

            if(!vis[i]) {

                int tmp = i, len = ;

                while(!vis[tmp]) {

                    vis[tmp] = ;

                    len++;

                    tmp = a[tmp];

                }

                ans = lcm(ans, len);

            }

        }

        cout<<ans<<endl;

    }

    return ;

}