Skip to content

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\)的那两个条件是满足的)。

Input Format

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

Output Format

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

Sample Input

41

Sample Output

20 40

Hint

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

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

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

Oops! 本题目还没有解答!

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

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

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