爱站程序员基地题目大意
今天，Tonnnny学习了一种称为Bogo Sort的新算法。 老师给了Tonnnny Bogo Sort的代码：
老师说，函数shuffle 是等概率地随机排列长度为n的数组a，这个算法的期望复杂度为O(n⋅n⋅n⋅n!n!n!)。
但是，Tonnnny是一个坚定的男孩——他一点也不喜欢随机！ 因此，Tonnnny改进了Bogo Sort。 他选择了一个最喜欢的长度为n的排列p，然后用排列p替换随机的shuffle，因此改进的算法，Tonnnny Sort，可以解决长度为n的数组的排序问题——至少Tonnnny如此认为。
Tonnnny对新算法感到满意，因此决定让您每天给他一个长度为N的不同数组，以使用Tonnnny Sort对其进行排序。
您是Tonnnny最好的朋友。 即使您发现该算法有某种错误，也希望让Tonnnny多快乐一会。 给定N和p，您需要计算Tonnnny可以开心的最大天数，因为在那之后，您将不能给Tonnnny一个可以用Tonnnny Sort排序的之前没出现过的数组。
答案可能非常大。 Tonnnny只喜欢最多N位的数字，因此请改为输出答案mod 10N10^N10N。
分析
题意是给一个1 ~ n 的数列，求其周期
考虑到n最大为10510^5105,所以要用高精度做
void cheng(ll x)//高精度乘法{for (int i=1;i<=len;i++) ans[i]*=x;for (int i=1;i<len;i++) if (ans[i]>9) ans[i+1]+=ans[i]/10,ans[i]%=10;while(len<n && ans[len]>9) ans[len+1]+=ans[len]/10,ans[len++]%=10;ans[len+1]=0;}
然后将序列里的每个环的周期求出来，答案就是这些环的lcm
然而，因为时间原因，以及高精度问题，lcm不能直接用gcd求
要先打质数表，用分解质因数的方法解决
AC代码
#include<bits/stdc++.h>#define ll long longusing namespace std;ll n,m,i,j,k,l,o,t,p,tot,len,cnt,pr[100006],pp[100005];ll a[100005],ans[100006],sz[100005],v[100005];void cheng(ll x){for (int i=1;i<=len;i++) ans[i]*=x;for (int i=1;i<len;i++) if (ans[i]>9) ans[i+1]+=ans[i]/10,ans[i]%=10;while(len<n && ans[len]>9) ans[len+1]+=ans[len]/10,ans[len++]%=10;ans[len+1]=0;}int main(){pr[1]=1;for (i=2;i<=100000;i++)if (!pr[i]){pp[++cnt]=i;for (j=2;j*i<=100000;j++)pr[j*i]=1;}scanf(\"%lld\",&n);ans[1]=1;len=1;for (i=1;i<=n;i++) scanf(\"%lld\",a+i);for (i=1;i<=n;i++)if (!v[i]){v[i]=1;sz[++tot]=1;for (j=a[i];j!=i;j=a[j])v[j]=1,sz[tot]++;}memset(pr,0,sizeof(pr));for (i=1;i<=tot;i++){for (j=1,t=0;j<=cnt&&sz[i]>1;j++){while(sz[i]%pp[j]==0) t++,sz[i]/=pp[j];pr[pp[j]]=max(pr[pp[j]],t);t=0;}}for (i=1;i<=cnt;i++) while(pr[pp[i]]--) cheng(pp[i]);for (i=len;i>=1;i--) printf(\"%lld\",ans[i]);}
