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）
Recommend liuyiding | We have carefully selected several similar problems for you: 5189 5188 5186 5185 5184
可以发现,每一项上面的指数,刚好是fib数 但是直接做指数太大,mod为素数 所以根据欧拉定理 mod的欧拉函数值为mod-1 a^b = a^(b%(mod – 1) 然后就可以做了
/*************************************************************************> File Name: hdu4549.cpp> Author: ALex> Mail: zchao1995@gmail.com> Created Time: 2015年03月16日 星期一 20时12分13秒 ************************************************************************/;const double pi = acos(-1.0);const int inf = 0x3f3f3f3f;const double eps = 1e-15;LL;typedef pair <int, int> PLL;const LL mod = 1000000006;class MARTIX{public:LL mat[3][3];MARTIX();MARTIX operator * (const MARTIX &b)const;MARTIX& operator = (const MARTIX &b);};MARTIX :: MARTIX(){memset (mat, 0, sizeof(mat));}MARTIX MARTIX :: operator * (const MARTIX &b)const{MARTIX ret;for (int i = 0; i < 2; ++i){for (int j = 0; j < 2; ++j){for (int k = 0; k < 2; ++k){ret.mat[i][j] += this -> mat[i][k] * b.mat[k][j];ret.mat[i][j] %= mod;}}}return ret;}MARTIX& MARTIX :: operator = (const MARTIX &b){for (int i = 0; i < 2; ++i){for (int j = 0; j < 2; ++j){this -> mat[i][j] = b.mat[i][j];}}return *this;}MARTIX fastpow(MARTIX A, int n){MARTIX ans;ans.mat[0][0] = ans.mat[1][1] = 1;while (n){if (n & 1){ans = ans * A;}n >>= 1;A = A * A;}return ans;}LL fast(LL a, LL n){LL b = 1;while (n){if (n & 1){b = a * b % 1000000007;}a = a * a % 1000000007;n >>= 1;}return b;}int main (){LL a, b, n;while (~scanf(“%lld%lld%lld”, &a, &b, &n)){MARTIX F;F.mat[0][0] = F.mat[0][1] = F.mat[1][0] = 1;if (n == 0){printf(“%lld\n”, a);continue;}if (n == 1){printf(“%lld\n”, b);continue;}MARTIX A;A.mat[0][0] = 1;A.mat[0][1] = 0;F = fastpow(F, n – 1);F = A * F;LL cnt1 = F.mat[0][1];LL cnt2 = F.mat[0][0];LL ans = fast(a, cnt1);ans = ans * fast(b, cnt2) % 1000000007;printf(“%lld\n”, ans);}return 0;}
旁观者的姓名永远爬不到比赛的计分板上。
