斐波那契公约数
题目描述
对于 Fibonacci 数列：
$$ f_i = \begin{cases}
[i = 1] & i \leq 1 \
f_{i – 1} + f_{i – 2} & i \gt 1
\end{cases}$$
请求出 $f_n$ 与 $f_m$ 的最大公约数，即 $\gcd(f_n, f_m)$。
输入格式
一行两个正整数 $n$ 和 $m$ 。
输出格式
输出一行一个整数，代表 $f_n$ 和 $f_m$ 的最大公约数。答案请对 $10^8$ 取模。
样例 #1
样例输入 #1
4 7
样例输出 #1
1
提示
数据规模与约定
- 对于 $100%$ 的数据，保证 $1 \leq n, m \leq 10^9$。
解题：
1. 传统 An = An-1 + An-2
An = An-1 + An-2 会超时
ll fb2(ll n)
{
ll temp1, temp2, temp;
// 第0项和第1项
temp1 = 1;
temp2 = 1;
// 斐波那契数列
for (unsigned long long i = 2; i <= n; i++)
{
temp = temp1 + temp2;
temp1 = temp2;
temp2 = temp;
cout << temp2 << " ";
}
return temp2;
}
2. 矩阵乘法
3. 快速倍增算法
- 快速倍增法简介
快速倍增法是一种高效计算斐波那契数列第 n 项的方法，其时间复杂度为 O(log n) 。该方法基于以下递推公式：
$$
\begin{cases}
F_{2k} = F_k \times [2F_{k+1} – F_k] \mod \text{MOD} \
F_{2k+1} = F_{k+1}^2 + F_k^2 \mod \text{MOD}
\end{cases}
$$
通过这些公式，可以将计算 ( F_n ) 的问题逐步拆分为更小的子问题，极大地减少了计算量。
递归实现：
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
#define MOD 1000000007
// Function calculate the N-th fibonacci
// number using fast doubling method
void FastDoubling(int n, int res[])
{
// Base Condition
if (n == 0) {
res[0] = 0;
res[1] = 1;
return;
}
FastDoubling((n / 2), res);
// Here a = F(n)
a = res[0];
// Here b = F(n+1)
b = res[1];
c = 2 * b - a;
if (c < 0)
c += MOD;
// As F(2n) = F(n)[2F(n+1) – F(n)]
// Here c = F(2n)
c = (a * c) % MOD;
// As F(2n + 1) = F(n)^2 + F(n+1)^2
// Here d = F(2n + 1)
d = (a * a + b * b) % MOD;
// Check if N is 偶数还是奇数
if (n % 2 == 0) {
res[0] = c;
res[1] = d;
}
else {
res[0] = d;
res[1] = c + d;
}
}
// Driver code
int main()
{
int N = 6;
int res[2] = { 0 };
FastDoubling(N, res);
cout << res[0] << "\n";
return 0;
}
迭代实现
// C++ program to find the Nth Fibonacci
// number using Fast Doubling Method iteratively
#include <bitset>
#include <iostream>
#include <string>
using namespace std;
// helper function to get binary string
string decimal_to_bin(int n)
{
// use bitset to get binary string
string bin = bitset<sizeof(int) * 8>(n).to_string();
auto loc = bin.find('1');
// remove leading zeros
if (loc != string::npos)
return bin.substr(loc);
return "0";
}
// computes fib(n) iteratively using fast doubling method
long long fastfib(int n)
{
string bin_of_n
= decimal_to_bin(n); // binary string of n
long long f[] = { 0, 1 }; // [F(i), F(i+1)] => i=0
for (auto b : bin_of_n) {
long long f2i1
= f[1] * f[1] + f[0] * f[0]; // F(2i+1)
long long f2i = f[0] * (2 * f[1] - f[0]); // F(2i)
if (b == '0') {
f[0] = f2i; // F(2i)
f[1] = f2i1; // F(2i+1)
}
else {
f[0] = f2i1; // F(2i+1)
f[1] = f2i1 + f2i; // F(2i+2)
}
}
return f[0];
}
int main()
{
int n = 13;
long long fib = fastfib(n);
cout << "F(" << n << ") = " << fib << "\n";
}
直接使用位运算实现
#include <iostream>
#include <numeric> // 包含 std::gcd
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uint;
const uint MOD = 100000000; // 1e8
// 结构体用于存储斐波那契数对 (F(k), F(k+1))
struct FibPair {
uint Fk; // F(k)
uint Fk1; // F(k+1)
};
// 迭代快速倍增法
FibPair fastDoubling(ull n) {
FibPair result = {0, 1}; // 初始化 F(0) = 0, F(1) = 1
ull current = n;
// 找到最高位的 1
int highestBit = 63 - __builtin_clzll(current);
for (int i = highestBit; i >= 0; i--) {
// 计算 F(2k) 和 F(2k+1)
ull twoFkp1 = (2 * (ull)result.Fk1) % MOD;
ull temp1 = (twoFkp1 + MOD - result.Fk) % MOD; // 2*F(k+1) - F(k) mod MOD
uint F2k = ((ull)result.Fk * temp1) % MOD; // F(2k) mod MOD
uint F2k1 = (((ull)result.Fk * result.Fk) % MOD + ((ull)result.Fk1 * result.Fk1) % MOD) % MOD; // F(2k+1) mod MOD
// 更新 F(k) 和 F(k+1)
result.Fk = F2k;
result.Fk1 = F2k1;
// 如果当前位是 1，则更新 F(k) 和 F(k+1) 为 F(2k+1) 和 F(2k+2)
if ((current >> i) & 1) {
uint temp = (result.Fk + result.Fk1) % MOD; // F(k+1) = F(k) + F(k+1) mod MOD
result.Fk = result.Fk1;
result.Fk1 = temp;
}
}
return result;
}
int main()
{
ull n, m;
cin >> n >> m;
// 计算 n 和 m 的最大公约数
ull tempmax = gcd(n, m);
// 如果 gcd(n, m) > 150000000，则取模 150000000
if (tempmax > 150000000)
tempmax = tempmax % 150000000;
// 计算斐波那契数列的第 tempmax 项
FibPair fibResult = fastDoubling(tempmax);
// 输出 F(n) mod MOD
cout << fibResult.Fk % MOD << endl;
return 0;
}