#P4294. [PA2015]Fibonacci

    ID: 3514 传统题 1000ms 64MiB 尝试: 204 已通过: 54 难度: 9 上传者: 标签>难度分类省选/NOI-博弈论周期规律验证枚举与搜索暴力枚举离线与分治分治算法数论扩展 CRT扩展欧几里得算法最小公倍数快速乘防溢出模数逐层提升CF2600

[PA2015]Fibonacci

[PA2015] Fibonacci

题目描述

定义斐波那契数列为

$$F_0=0,\qquad F_1=1,\qquad F_m=F_{m-1}+F_{m-2}\quad (m\ge2).$$

给定一个数字串 SS,找一个下标 kk,使 FkF_k 的十进制表示以 SS 结尾。FkF_k 使用通常的十进制表示,不能通过在前面补零来匹配 SS。

输入格式

一行一个由 11 至 1818 个十进制数字组成的字符串 SS。SS 可以以零开头。

输出格式

若存在符合条件的整数 kk,输出任意一个满足 0≤k<101000\le k<10^{100} 的解。若无解,输出 NIE。

样例 #1

样例输入 #1

025

样例输出 #1

1525

样例 #2

样例输入 #2

222

样例输出 #2

NIE

Potyczki Algorytmiczne 2015 原题