T1.Crazy

题意:求$\sum\limits_{i=1}^{n}{Fib[i]^2}$其中Fib[i]表示斐波那契数列第i项,Fib[1]=Fib[2]=1;(n<=1e15)
分析:通过猜想与验证,我们发现$\sum\limits_{i=1}^{n}{Fib[i]^2}=Fib[n]\times Fib[n+1]$
证明:显然这个结论对于n=1是成立的。我们假设这个结论是正确的,那么有
$$
\sum\limits_{i=1}^{n}{Fib[i]^2}=\sum\limits_{i=1}^{n-1}{Fib[i]^2}+Fib[n]^2=Fib[n-1]Fib[n]+Fib[n]^2=Fib[n]Fib[n+1]
$$
然后我们可以用矩阵快速幂来求Fib[i]


T2.lucky
题意:对于区间[L,R]内求有多少个数是LN的倍数且不是任何一个BN的倍数(BN个数<=15,1<=L,R<=1e15)
分析:容斥搞一搞,但要注意$\prod BN$越界后直接返回


T3.feed
题意:用两个给定大小的勺子把无限多的粥转移到无限大的碗里或转移出去,每次勺子必须装满。求碗里能否有X单位的粥。
分析:扩展欧几里得。
我们需要知道对于ax+by=c的通解表达式,并且将表达式表示成坐标系中的直线,求两条直线纵坐标绝对值的和的最小值。