上篇文章末尾我们说学了欧几里得算法一定给大家更新。

今天它来了！

欧几里得算法

欧几里得算法是一种求最小公倍数和最大公因数的算法。

我们看图：

我们把两个数看成长方形，在长方形内不断划分出小正方形，PS：第一个的边长是两数中较小的那个，后面的边长就是边长与边长相减，最后那个最小的小正方形的边长就是他们的最大公因数 （也就是最后一个除数）。

其实说白了就是小学奥数里的辗转相除法。

那我们就把两个数不断地相处，余数就当下一次的除数，除数就当下一次的被除数，直到余数为0。这个操作我们封装在函数里。

PS：求出最大公因数就可以求最小公倍数。

改代码

还记得上次做的无聊的军官吗？

那段代码会超时，求最小公倍数时间太长。

哎，学完欧几里得算法后我们就可以改一改了。

把最后一段求最小公倍数的代码删掉。

但是我们要注意，题目中还说答案在64位整数范围之内。

我们就不能将函数用作int类型。

那什么类型是64位呢？

答：无字符longlong（unsigned long long）。

所有和计算最小公倍数相关的变量或数组都要改成这个类型。

接下来上代码！

#include<bits/stdc++.h>
using namespace std;
int a[100005],o[1000005],w,sum,flag[1000005],cnt,gys;
unsigned long long gbsh,b[100005];    //与函数相关 
unsigned long long gcd(unsigned long long x,unsigned long long y)    //求最大公因数 
{
	unsigned long long r=x%y;   //初始的余数 
	while(r!=0)   //余数为0就结束 
	{
		x=y;   //除数变成被除数 
		y=r;   //余数变成除数 
		r=x%y;   //更新余数 
	}
	return y;   //返回最大公因数 
}
unsigned long long lcm(unsigned long long x,unsigned long long y)    //求最小公倍数 
{
	return x*y/gcd(x,y);   //返回最小公倍数 
}
int main()
{
	//其余相同 
	int i,sum=0,n,j;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(i=1;i<=n;i++)
	{
		if(flag[i]==0)
		{
			w=i;
			sum=1;
			flag[w]=1;
			while(1)
			{
				if(flag[a[w]]==0)
				{
					sum++;
					flag[a[w]]=1;
				}
				else
				{
					break;
				}
				w=a[w];
			}
			cnt++;
			b[cnt]=sum;
		}
	}
	//此处不同 
	gbsh=1;   //不能为0 
	for(i=1;i<=cnt;i++)   //多个数求最小公倍数 
	{
		gbsh=lcm(gbsh,b[i]);   //调用函数 
	}
	cout<<gbsh<<endl;  //输出
	return 0;    //潇洒结束 
}

感谢阅览！烦请一键三连！Thanks♪(･ω･)ﾉ