1127.换位置游戏 代码

代码

#include<iostream>
#include<stdio.h>
using namespace std;
int n,a[2001],l,ans,m,k,c[2001],x,y;
bool b[2001],f[1001];
int gcb(int a, int b)//最大公约数函数
{
    int c = 0;
    while(c = a % b)
    {
        a = b;
        b = c;
    }
    return b;
}
int main()
{
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    cin>>n;
    m=n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]==i)
        {
            b[i]=1;
            m--;
        }
    }
    if(m==0)//测试是否全部到位，减少时间复杂度
    {
        cout<<1;
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        if(b[i]!=1)
        {
            l=0;
            int k=i;
            while(1)
            {
                if(k==i && l==1)//l为标记
                {
                    break;
                }
                else
                {
                    l=1;
                }
                k=a[k];//进行模拟了
                ans++;//ans表示当前轮数
            }
            f[ans]=1;//作为最小公倍数的参数之一
            ans=0;
            l=0;
        }
    }
    for(int i=2;i<=1000;i++)//求最小公倍数，因为1与任何数的 最小公倍数 都为那个数，所以i=2
    {
        if(x==0)//选择第一个参数（初始化）
        {
            if(f[i]==1)
            {
                x=i;
            }
        }   
        else
        {
            if(f[i]==1)//判断是否出现
            x=x*i/gcb(x,i);//求最小公倍数，关于为什么父题解在 最后一行 提到过
        }
    }
    cout<<x; //输出最小公倍数
}