hdu 5392 Infoplane in Tina Town

题目

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5392

题意

给定一个置换a,求序列1-n经过多少次a置换能够再次变回序列1-n

分析

题意很明显,是求置换群的循环长度。

根据数论中的内容,循环长度等于所有循环节长度的最小公倍数,因此只要计算所有循环节的长度即可。

但是题目中提到需要对最后的答案进行求模处理,然而欧几里得算法求最小公倍数无法去模,因此要用质因数分解法进行求最小公倍数