M斐波那契数列F[n]是一种整数数列,它的定义如下:
F[0] = a F1 = b F[n] = F[n-1] * F[n-2] ( n > 1 )
现在给出a, b, n,你能求出F[n]的值吗?
输入包含多组测试数据; 每组数据占一行,包含3个整数a, b, n( 0 <= a, b, n <= 10^9 )
对每组测试数据请输出一个整数F[n],由于F[n]可能很大,你只需输出F[n]对1000000007取模后的值即可,每组数据输出一行。
0 1 0 6 10 2
0 60
$fib(0) = 0$ $fib(1) = 1$ $fib(n) = fib(n-1)+fib(n-2)$ | n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | … | … | n-1 | n | | —–: | —–: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | | fib(n) | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | 233 | 377 | … | … | fib(n-1) | fib(n) |
$$ A_{n} = \begin{bmatrix} fib(n) & fib(n+1) \ fib(n+1) & fib(n+2) \ \end{bmatrix} $$
$A_{0} = \begin{bmatrix}0 & 1 \1 & 1 \ \end{bmatrix} $ $A_{1} = \begin{bmatrix}1 & 1 \1 & 2 \ \end{bmatrix} $ $ A_{2} = \begin{bmatrix}1 & 2 \2 & 3 \ \end{bmatrix} $ $A_{3} = \begin{bmatrix}2 & 3 \3 & 5 \ \end{bmatrix} $ $A_{4} = \begin{bmatrix}3 & 5 \5 & 8 \ \end{bmatrix} $ … … …
$A_{n} = \begin{bmatrix}fib(n) & fib(n+1) \ fib(n+1) & fib(n+2) \ \end{bmatrix} $
$A_{1} = \begin{bmatrix}1 & 1 \1 & 2 \ \end{bmatrix} = A_{0}A_{0}$ $ A_{2} = \begin{bmatrix}1 & 2 \2 & 3 \ \end{bmatrix} = A_{0}A_{0}A_{0}$ $A_{3} = \begin{bmatrix}2 & 3 \3 & 5 \ \end{bmatrix} = A_{0}A_{0}A_{0}A_{0} $
$ A_{4} = \begin{bmatrix}3 & 5 \5 & 8 \ \end{bmatrix} = A_{0}A_{0}A_{0}A_{0}A_{0}$ $A_{n} = \begin{bmatrix}fib(n) & fib(n+1) \fib(n+1) & fib(n+2) \ \end{bmatrix} = A_{0} ^ {n+1}$
\begin{array}{|rrrrrrrr|} \hline \color{red}{综上所述,要想求解f(n),求得A(n)或者A(n-2)即可} & \hline \end{array}
Q: 求解 $ x ^ N $ A: O(N)的算法:
ans = 1;
for(i = 1; i <= n; i++){
ans *= x;
}
A: O(logN)的算法:
举个例子:计算 $ x ^ {22} $
\begin{array}{|rrrrrrrr|} \hline & \color{red}{CODE:}& \hline \end{array}
typedef long long LL;
// 计算x^n,复杂度O(logN)
LL powN(LL x, LL n){
LL r = 1; // 计算结果
while(n){
if(n&1) r *= x; // 如果n的二进制表示i(i >= 0)的位置是1,则乘上x^(2^i)
x *= x; // 将x平方
n >>= 1; // 右移一位
}
return r; // 返回结果
}
// 计算x^n mod p, ( a * b ) % p = ( ( a % p ) * ( b * p ) ) % p 复杂度O(logN)
LL mod_powN(LL x, LL n, LL p){
LL r = 1; // 计算结果
while(n){
if(n&1) r = r * x % p; // 如果n的二进制表示i(i >= 0)的位置是1,则乘上x^(2^i)
x = x * x % p; // 将x平方
n >>= 1; // 右移一位
}
return r; // 返回结果
}
费马小定理是数论中的一个定理:假如a是一个整数,p是一个质数,那么 $a^{p}-a$是p的倍数,可以表示为 $$ a ^ p \equiv a (\mod p) $$ 如果a不是p的倍数,这个定理也可以写成 $$ a ^ {p-1} \equiv 1 (\mod p)$$ 费马小定理是欧拉定理的一个特殊情况:如果n和a的最大公因数是1,那么 $$ a^{φ(n)} \equiv 1 (\mod n) $$ 这里φ(n)是欧拉函数。欧拉函数的值是所有小于或等于n的正整数中与n互质的数的个数。假如n是一个素数(质数),则φ(n) = n-1,即费马小定理 注: $\equiv$是同余符号 $ a \mod p = b \mod p$ 可表示为 $ a \equiv b (\mod p)$
推导以下表达式: 当p是质数时: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$ 成立
证: $$ n = k(p-1) + (n \mod (p-1)) (k为整数) $$ $$ a ^ n \equiv a ^ {k(p-1) + (n \mod (p-1))} \equiv {a ^ {p-1}} ^ {k} a ^ {(n \mod (p-1))} (\mod p)$$ 由费马小定理可知: $$ {a ^ {p-1}} ^ {k} \equiv a ^ {p-1} \equiv 1(\mod p)$$ 得证: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$
我们注意到虽然题目中的M斐波那契数列和斐波那契数列有异曲同工之处,但是一个计算的是乘法,一个是加法,但加法和乘法之间有着密切的联系.
先计算前几项的值: $$ f(0) = a = a ^ 1 b ^ 0 $$ $$ f(1) = b = a ^ 0 b ^ 1 $$ $$ f(2) = a b = a ^ 1 b ^ 1 $$ $$ f(3) = a b b = a ^ 1 b ^ 2 $$ $$ f(4) = a a b b b = a ^ 2 b ^ 3 $$ $$ f(4) = a a a b b b b b= a ^ 3 b ^ 5 $$ $$ ……………………………………………………..$$ $$ f(n) = f(n-1)f(n-2) = a ^ x b ^ y $$ |n| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 11 | 12 | 13 | … | … | n-1 | n | |——–| —–: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | :—-: | |x| 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | … | … | fib(n-2) | fib(n-1) | |y| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 | … | … | fib(n-1) | fib(n) |
不难得出: $$ f(0) = a $$ $$ f(1) = b $$ $$ f(n) = f(n-1)f(n-2) = a ^ {fib(n-1)} b ^ {fib(n)} (n >= 2) $$
通过上面费马小定理证明的结论,当p是质数时: $$ a ^ n \equiv a ^ {(n \mod (p-1))} (\mod p) $$ 所以我们实际上需要计算的就是下面的表达式(p = 1000000007): $$ f(n) \mod p= f(n-1)f(n-2) \mod p = a ^ {fib(n-1) \mod p-1} b ^ {fib(n) \mod p-1} \mod p(n >= 2) $$
1.计算类似于计算整数的快速幂算法计算矩阵的幂 $A_{n-1} = A_{0} ^ {n}$ $A_{0} = \begin{bmatrix}0 & 1 \1 & 1 \ \end{bmatrix}$ $A_{n-1} = \begin{bmatrix}fib(n-1) & fib(n) \fib(n) & fib(n+1) \ \end{bmatrix} = A_{0} ^ {n}$
计算矩阵的幂时,我们实际上需要得到的结果是: $$ A_{n-1} \mod p-1 = \begin{bmatrix}fib(n-1) \mod p-1 & fib(n) \mod p-1 \fib(n) \mod p-1 & fib(n+1) \mod p-1 \ \end{bmatrix} = (A_{0} \mod p-1) ^ {n} \mod p-1 $$
如果理解了上面的快速幂算法的话,这实现起来将会非常简单
2.得到$fib(n-1) \mod p-1$ 和 $fib(n) \mod p-1$ 之后,设这两个数为x,y,用整数的快速幂算法计算: $$a ^ x b^y \mod p = (a ^ x \mod p b^y \mod p) \mod p$$
\begin{array}{|rrrrrrrr|} \hline & \color{red}{CODE:}& \hline \end{array}
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD1 = 1e9+7; // p
const int MOD2 = 1e9+6; // p-1
LL a,b,n;
typedef struct Matrix{ // 矩阵结构体
LL arr[2][2];
}Matrix;
Matrix unit = { // 单位矩阵
1,0,
0,1
};
Matrix A0 = { // A0矩阵
0,1,
1,1
};
// 矩阵a*b
Matrix matrixMulti(Matrix a, Matrix b){
int i,j,k;
Matrix tmp;
for(i = 0; i < 2; i++){
for(j = 0; j < 2; j++){
tmp.arr[i][j] = 0;
for(k = 0; k < 2; k++){
tmp.arr[i][j] += (a.arr[i][k]*b.arr[k][j])%MOD2;
tmp.arr[i][j] %= MOD2;
}
}
}
return tmp;
}
// 矩阵快速幂,计算的结果对MOD2取余
Matrix matrixPow(Matrix a, LL n){
Matrix r = unit, base = a;
while(n){
if(n&1) r = matrixMulti(r,base);
base = matrixMulti(base, base);
n >>= 1;
}
return r;
}
// 整数快速幂,计算的结果对MOD1取余
LL powN(LL a, LL n){
LL r = 1, base = a%MOD1;
while(n){
if(n&1) r = r*base%MOD1;
base = base*base%MOD1;
n >>= 1;
}
return r;
}
int main(){
//freopen("in.txt", "r", stdin);
Matrix An_1;
while(~scanf("%lld%lld%lld", &a, &b, &n)){ // 输入a,b,n
An_1 = matrixPow(A0,n); // 计算An_1
printf("%lld\n", powN(a, An_1.arr[0][0]) * powN(b, An_1.arr[1][0]) % MOD1);
}
return 0;
}
Q: 为什么要使用费马小定理? A: 因为 $ x \mod p-1 <= x $ 所以可以减少计算整数幂时候的计算次数,不使用费马小定理会超时.