原题链接:https://ac.nowcoder.com/acm/contest/5670/E

题目描述

老师教给Tonnnny不知道在干啥的新奇的Bogo Sort算法，但小猴子Tonnnny感觉难受的一批，改进出了自己的猴算法Monkey Sort。但闲的一批细心的你发现了错误，可是作为猴之友Tonnnny最好的朋友，你不忍心让他伤心，于是你又多了一项任务，所以你要每天给出规定的长度为N的数组让Tonnnny排序，让他变得更忙碌开心。求这个天数，即最多能排列几次。

输入描述

第一行输入一个N（1 N ）
第二行输入一行数组p，确保每个数字最终排列后均为1,2,3,...,N。

输出描述

输出Tonnnny最多能开心的天数，即最多能排列的次数，并取余 。

样例

• 样例1
  输入
  5
  1 2 3 4 5
  输出
  1
• 样例2
  输入
  6
  2 3 4 5 6 1
  输出
  6

题解

首先看要模的部分就可以猜想这需要恶心的高精度；
其实题目所给的数组其实就是个环，然后脑袋一拍就能想到（然而其实把脑袋拍破了也不一定想得到），需要求这些环的长度的最小公倍数；
那么问题来了，在高精度的前提下求lcm对于像作者这样的蒟蒻来说可不是一件eazy的事情。但相比之下，先分解质因数就会显得简单一些；
这样就剩下最后一个问题，如何把这篇题解写得更完美一些题目最后要求一个麻烦的一批的取模，但实际上是不要的，因为lcm最多就N位。

参考代码

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

int n,t,len,cnt,v;
int a[MAXN],b[MAXN],ans[MAXN],pri[MAXN],irp[MAXN],w[MAXN];
void mul(int 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;
    }
    a[len+1]=0;
}
int main()
{
    ans[1]=1,len=1;
    for(int i=2;i<MAXN;i++)//分解质因数
    {
        if(!pri[i])
        {
            for(int j=i*2;j<MAXN;j+=i)
                pri[j]=1;
            irp[++cnt]=i;
        }
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);

    for(int i=1;i<=n;i++)
    {
        if(!w[i])
        {
            w[i]=1;
            b[++v]=1;
            for(int j=a[i];j!=i;j=a[j])
            {
                w[j]=1;
                b[v]++;
            }
        }
    }
    memset(pri,0,sizeof(pri));
    for(int i=1;i<=v;i++)
    {
        for(int j=1,t=0;j<=cnt&&b[i]>1;j++)
        {
            while(b[i]%irp[j]==0)t++,b[i]/=irp[j];//求质因数个数
            pri[irp[j]]=max(pri[irp[j]],t);
            t=0;
        }
    }
    for(int i=1;i<=cnt;i++)
        while(pri[irp[i]]--)mul(irp[i]);
    for(int i=len;i>0;i--)printf("%d",ans[i]);
}