https://ac.nowcoder.com/acm/contest/5670
Bogo sort（高精度（lcm+大数处理）+群论（循环节长度））
思路：
来自https://ac.nowcoder.com/acm/contest/view-submission?submissionId=44402547 和 https://blog.nowcoder.net/n/59a8480b4bbf4e69b1523bbaa07a0c7e
- 如果一个置换中没有环，如{1,2,3}，只能找出一个符合条件的原排列：{1,2,3}。
- 如果有一个环，如{3,1,2}，由于环的长度为3（不同元素的数量），所以可以找出三种原排列：{1,2,3},[2,3,1},{3,1,2}。
- 如果有两个环，如{2,1,4,3}，由于两个环的长度分别为2（不同元素的数量），所以可以找出两种原排列：{1,2,3,4},[2,1,4,3}。
不难得出，如果有一个长度为n的环，那么可以找出n个原序列；而有多个环的时候，可以找出这些环长度的lcm。由于长度总和就是n，所以他们的lcm一定不会大于n位，不需要取模。
高精度
问题是高精度求lcm是个麻烦的事情，万幸的是，这些群的大小都是int型的，因此gcd是很好求的。
可是要用到大数除，诶这就有点麻烦了，对于一个根本忘了怎么写高精度的蒟蒻来说，除法是个难于上青天的事情。
但是蒟蒻脑子好使，可以用另一种方式来求lcm。考虑分解质因数，对于每个质数记录每个数的质因数的个数的最大值，有点绕呵，举个例子吧。
比如有2,3,42,3,42,3,4要求它们的最小公倍数，则我只要分解：
2=2,3=3,4=2*2
那么2有max(1,2)次，3有1次，因此它们的最小公倍数是2^2*3^1=12，没有问题。
它的原理是：任意一对数，它们如果有质因子相同，那么根据lcm=a*b/gcd可知，它会将公共的部分除掉，相当于对于每个质因子的个数求个max即可。
比如有质数pr，a=pr^3*……，b=pr^5*...，则它们的公共部分是pr^3，相乘之后有pr^8，除掉后有pr^5 也就是pr^{max(3,5)}
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+4; int n,m,l=1,cnt,vis[maxn],prime[maxn],p[maxn],ans[maxn],len[maxn]; //大数乘 void multi(int x){ for(int i=1;i<=l;i++) ans[i]*=x; for(int i=1;i<l;i++) if(ans[i]>9) ans[i+1]+=ans[i]/10,ans[i]%=10; while(l<n&&ans[l]>9) ans[l+1]+=ans[l]/10,ans[l++]%=10; ans[l+1]=0; } int main(){ ans[0]=0,ans[1]=1; for(int i=2;i<maxn;i++) //筛质数 if(!vis[i]){ for(int j=i*2;j<maxn;j+=i) vis[j]=1; prime[++cnt]=i; } scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&p[i]); memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++){ //找每个循环节的长度 存在len中 if(vis[i]) continue; vis[i]=len[++m]=1;int j=p[i]; while(j!=i) vis[j]=1,len[m]++,j=p[j]; } memset(vis,0,sizeof(vis)); for(int i=1;i<=m;i++) //找每个循环节长度的因子，找出lcm（每个质数出现的最多次数） for(int j=1;j<=cnt;j++){ if(len[i]<=1) break; int tmp=0; while(len[i]%prime[j]==0) tmp++,len[i]/=prime[j]; vis[prime[j]]=max(vis[prime[j]],tmp); } for(int i=1;i<=cnt;i++) while(vis[prime[i]]--) multi(prime[i]); //大数乘 for(int i=l;i>=1;i--) printf("%d",ans[i]); //倒序输出 printf(" "); }