昨晚紫书看到,以为很水,要写的时候一堆麻烦QwQ
题目链接
(紫书P316)
题意:
Fibonacci数列
f(0) = 0
f(1) = 1
f(i) = f(i - 1) + f(i - 1), (i >= 2)
给出a, b, n,求f($a^b$) mod n.
解法:
设F(i) = f(i) % n
那么当F(i) = F(0), F(i + 1) = F(1)时, 0i-1就是一个循环节n-1中选两次)开始循环
这个循环节多长呢?余数最多n个,所以最多$n^2$项(0
n最大是1000,所以循环节最大就是1e6
算出循环节后,再算出$a^b$是第几项就行了 (就是F($a^b$)=F($a^b$ mod n))
题目给出的a和b爆了long long……但是unsigned long long还是能存得下
unsigned long long的占位符是%llu,或者直接cin读入
代码:
1 |
|