11410: 【原1410】首长的虐狗计划2

author: 陈天垚&陈仪宁原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1410

Description

首长的妹子小时候睡觉前常常会玩一个游戏。

两只手分别表示一个数字，刚开始是1 1（或者其它两个相同的数字），之后每一轮两只手轮流碰一下另一只手，然后将这只手上的数字加上另一只手上的数字，再对10（某个数\(M\) ）取余数。

游戏玩久了，妹子渐渐发现，刚开始的两个数如果是一样的，那么之后肯定又会出现两个数一样的情况。

后来妹子碰到了首长，和首长一起玩这个游戏。

好奇的首长玩着玩着想到一个问题，如果从1 1开始，再一次出现两个数一样会是什么时候，这两个数又会是什么呢？

首长想了很久很久，发现以自己的智商只能解决\(M\)是素数并且： \[ 5^{\frac{M-1}{2}}\equiv1\pmod{M} \] 的情况。

其它的情况首长是在想不出来，于是无奈之下请教了辣酱。结果辣酱也不会……

所以首长只能出他会做的部分给你们做了（也就是说关于\(M\)的那两个条件是满足的）。

一行一个整数\(M\)。

一行两个整数，分别代表第几轮之后会出现两个数相同的情况与出现的数是什么。

20 40

对于\(50\%\)的数据，\(N\leq10^5\)。

对于\(80\%\)的数据，\(N\leq10^9\)。

对于\(100\%\)的数据，\(N\leq10^{11}\)。

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！