背景

据说noip快开始了,同学们还没有复习基础数论于是我为这水一题。

描述

很久以前,13世纪初期,Leonardo Pisano提出fibonacci数列的概念:不妨用fib_n表示第n个fibonacci数,则当n≤2时fib_n=1;当n>2时fib_n=fib_{n-2}+fib_{n-1}

据说,在某一个平行世界里,fibonacci数的概念也是存在的,但是它是凭借另外一种形式存在,不妨仍然使用fibonacci数代表这个概念,然而与众不同地,在这个平行世界里,当n≤2时fib_n=1;当n>2时fib_n=a*fib{n−2}+b*fib_{n-1}。每个拥有专属fibonacci数的人是幸运的,换句话说,没有自己的fibonacci数的人是不幸的。

造物主不忍心告诉不幸的人他是不幸的,因此,每一个人,无论幸运或是不幸,都被赋予了一个数字。如果一个人是幸运的,那么这个数字一定是他自己专属的fibonacci数在某个质数p的剩余系内的表示,否则,这个数字仅仅是造物主和他开的一个玩笑,或者说,一个善意的谎言。

在这个世界里,你是一个幸运的人,你得到了获知这个平行世界的a,b以及造物主对每一个人使用的模数的能力,也因此而获知自己是一个幸运的人。

你的两位好朋友很羡慕你,而且他们希望你也能帮助他们获知自己是否受到幸运之神眷顾,他们都知道你是一个注重情义的人,你一定会帮助他们的,对吗?

输入格式

第一行有两个整数a和b。

第二行有两个正整数y1和p1,表示第一个朋友被赋予的数字是y1,造物主对他使用的模数是p1。

第三行有两个正整数y2和p2,表示第二个朋友被赋予的数字是y2,造物主对他使用的模数是p2。

输出格式

共有两行,每一行对应一位朋友的询问,如果他是一个幸运的人,输出一个最小正整数x,表示他的专属fibonacii数是fib_x,但是如果他是一个不幸的人,输出"Unfortunately",表示他是不幸的。

样例输入

1 1
14 19
15 19

样例输出

Unfortunately
9

数据范围与约定

  • 对于30%的数据:a=-1,p\le10^7
  • 对于75%的数据:a=±1,p\le10^9
  • 对于100%的数据:0\le|a|\le1,0\le|b|\le23333,0\le y_i<p_i<2^{31}

样例解释

在模19的剩余系内,fibonacci数列前二十项为1,1,2,3,5,8,13,2,15,17,13,11,5,16,2,18,1,0,1,1。

来源

原创