hdu4549

maksyuki 发表于 oj 分类,标签: ,
0

M斐波那契数列

Problem Description

M斐波那契数列F[n]是一种整数数列,它的定义如下:

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n,你能求出F[n]的值吗?

Input

输入包含多组测试数据;
每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )

Output

对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模后的值即可,每组数据输出一行。

Sample Input

0 1 0

6 10 2

Sample Output

0

60

Source

2013金山西山居创意游戏程序挑战赛——初赛(2)

 

题目类型:费马小定理降幂+矩阵快速幂取模

算法分析:首先要发现a和b的指数值分别按照斐波那契数列的规律递增。最后计算的是a^k1 * b^k2 % p,则等价于求解((a^k1 % p) * (b^k2 % p)) % p。比如求解a^k1 % p的值,此时由于递推之后k1比较大,且模值p是一个素数,则使用费马小定理进行降幂。而且k1的求解需要使用矩阵加速,记住此时模值应该是p - 1!!!