E-Bogo Sort

题目链接：https://ac.nowcoder.com/acm/contest/5670/E
题目大意：
求可以通过这个函数排好序的排列个数。

这个的shuffle实现的功能就是让a[i] = b[p[i]],把原来p[i]位置的a放到i位置。
我们画个图来看看。

我们可以把这个环想象为一个在转圈圈的传送带，1，2，3...,n通过这个环的转动来生成的排列都可以再通过环的转动来转回1，2，3...n，也就是说我们要去求这些置换的循环节。每次转的时候是所有环一起转，因此转lcm次才能转回最开始的样子。
这题在代码实现上：
1.需要考虑怎么去考虑这个环。
2.因为很多个数的lcm最后可能很大，因此还需考虑如何求很多数的lcm
由于cycle 长度总和是n，所以一定不会大于n 位数，不取模即可。
最长的答案也就几百位(比赛时不放心大不了打表验证一下)。
来自
代码：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e5+5;

vector<int> cheng(int x, vector<int> vv)
{
    vector<int> ans;
    int t = 0;
    int i;
    for(i=0; i<vv.size(); i++)
    {
        t=t+vv[i]*x;
        ans.push_back(t%10);
        t/=10;
    }
    while(t>0)
    {
        ans.push_back(t%10);
        t/=10;
    }

    return ans;
}

bool vis[maxn];
int num[maxn];
int a[maxn];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
    int s;
    vector<int> ans;
    ans.pb(1);
    for(int i = 1; i <= n; i++)
    {
        if(vis[i] == 0)
        {
            s = 0;
            int k = i;
            while(vis[k] == 0)
            {
                vis[k] = 1;
                k = a[k];
                s++;
            }
        }
        for(int i = 2; i * i <= s; i++)
        {
            int cnt = 0;
            while(s % i == 0)
            {
                s /= i;
                cnt++;
            }
            num[i] = max(num[i],cnt);
        }
        if(s > 1)
        {
            num[s] = max(num[s], 1);
        }
    }
    for(int i = 2; i <= n; i++)
    {
        for(int j = 0; j < num[i]; j++)
        {
            ans = cheng(i,ans);
        }
    }
    int f = 1;
    for(int i = ans.size()-1; i >= 0; i--)
    {
        if(ans[i] != 0 || f == 0)    //去前导零 
        {
            f = 0;
            printf("%d",ans[i]);
        }
    }
    printf("\n");
    return 0; 
}