#P8560. [2019年备战noi]兔子

    ID: 8647 传统题 1000ms 256MiB 尝试: 12 已通过: 5 难度: 7 上传者: 标签>数论动态规划组合数学CF2300模运算数学矩阵

[2019年备战noi]兔子

兔子(rabbit)

题目描述

兔子每月的对数以如下数学模型为准。令 P=109+9P=10^9+9:

$$F_1=F_2=1,\qquad F_n=(F_{n-1}+F_{n-2})\bmod P\quad(n\ge3).$$

给定 KK,求满足 Fn=KF_n=K 的最小正整数月份 nn。如果没有解,输出-1。 月份从1开始计数;即使 K=0K=0,也必须求第一次出现0的正整数月份,不能输出0。

输入格式

一行一个整数 KK。

输出格式

输出一行一个整数,表示最小正整数月份;无解输出-1。

样例

3
4

数据范围

0≤K<109+90\le K<10^9+9。

  • 30%的数据:有解时答案不超过 10610^6。
  • 另外30%的数据:有解时答案是偶数。

参考附件

原题资料(本页约定为准)