牛客9场 A （菜鸡题解）

查了一晚上资料加牛客群的大佬提供帮助，终于是搞懂了这道 The power of Fibonacci
经过一天的爬坑，最后在OI Wiki上找到一个fib有一个取模循环节，就是可以在p^2-1以内
找到下一个 0 1 1 ...的fib序列，也就是说，累加前n个fib就可以变成按以下计算
（假设模1000000000的循环节是N）

ans=n/N×F[N]+F[n%N]
这样做确实可行，但是这个N太大了是1500000000（我自己在电脑上跑了10几秒跑出来的），
所以这题要是这样做绝对TEL，然后，在一观察大佬代码，加群里大佬提供的链接
http://webspace.ship.edu/msrenault/fibonacci/fibfactory.htm
将512 和 1953125 运行一下，得到了4个熟悉的数据。
(这不就是A题代码最短的4个数字吗，注：Period就是表示模输入数字下fib的循环节N)


这512=2^9 1953125=5^9 而1e9=2^9*5^9 所以大家懂了吧 这几个数怎么来的了。(1e9是模数，而且2和5是素数)
然后知道这个有啥用？
我们可以快速解出n m下模512的值和模1953125的值。

• ans%512=x
• ans%1953125=y
• (ans假设为不取模的答案累加n项的和)
• 我们最后要求的是
• ans%(512×1953125)得到最后的答案，根据取模的性质我们进行以下转换。
• ans=q×1e9+d (ans%1e9=d)
• （q×1e9+d）%512=d%512=x
• （q×1e9+d） %1953125=d%1953125=y
  所以最后我们惊讶的发现，d满足以上两个要求的，累加1953125到y上来满足模512等于x

(住：第一次写，有啥不合理的或者侵权之类的，及时联系我，我会删除的。还有感谢群里大佬们的解惑,菜鸡一个，反正赛场我是想不出来的。因为花了好长功夫弄懂，就想写下来，有不对的请立马指正，误导了别人就不来好了。)