题解

先看这道题的歪解
可知当$n>m$时，$fib_{n}=fib_{m+1}fib_{n-m}+fib_{m}fib_{n-m-1}$.

$\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m}+fib_{m}fib_{n-m-1},fib_m)$.

又$\because fib_mfib_{n-m}|fib_m,$

$\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m},fib_m)$(辗转相除法).

又$\because \gcd(fib_n,fib_{n-1})$
$=\gcd(fib_{n-2},fib_{n-1})$(辗转相除法)
$=\gcd(fib_{n-2},fib_{n-3})$(辗转相除法)
$=\gcd(fib_{n-4},fib_{n-3})$(辗转相除法)
$=\gcd(fib_{n-4},fib_{n-5})$(辗转相除法)
$=…$
$=\gcd(fib_{1},fib_{2})$
$=1$,

$\therefore \gcd(fib_n,fib_m)=\gcd(fib_{m+1}fib_{n-m},fib_m)=\gcd(fib_{n-m},fib_m)$.

嗯？怎么有点眼熟？
那这样不就可以和普通的求最大公因数一样了吗！

$\therefore \gcd(fib_n,fib_m)=\gcd(fib_{n-m},fib_m)=\gcd(fib_{n\mod m},fib_m)=\gcd(fib_{\gcd(n,m)},fib_{\gcd(n,m)})=fib_{\gcd(n,m)}$.

所以，我们只需要求$fib_{\gcd(n,m)}$的值就行了
矩阵快速幂：

#include <iostream>
#include <cstdio>
#include <memory.h>
using namespace std;
const int mod = 1e8;
struct node{
	long long a[2][2];
	node(){
		memset(a, 0, sizeof(a));
	}
	node operator * (const node &b) const{
		node tmp;
		for(int i = 0; i < 2; i++){
			for(int j = 0; j < 2; j++){
				for(int k = 0; k < 2; k++){
					tmp.a[i][j] = (a[i][k] * b.a[k][j] % mod + tmp.a[i][j]) % mod;
				}
			}
		}return tmp;
	}
};
node pow(node n, int k){
	node tmp;
	tmp.a[0][0] = tmp.a[1][1] = 1;
	while(k){
		if(k & 1) tmp = tmp * n;
		n = n * n, k >>= 1;
	}return tmp;
}
int gcd(int n, int m){
    if(m == 0) return n;
    return gcd(m, n % m);
}
int main(){
	int n, m;
	cin >> n >> m;
    if(n < m) swap(n, m);
    n = gcd(n, m);
	node a;
	a.a[0][0] = a.a[0][1] = a.a[1][0] = 1;
	cout << pow(a, n).a[1][0];

	return 0;
}

时间复杂度：$O(\log_2n)$.
乘法分治：

#include <iostream>
#include <cstdio>
#include <map>
#include <algorithm>
#define int long long
using namespace std;
map <int, int> a;
const int mod = 1e9 + 7;
int fib(long long n){
	if(a[n]) return a[n];
	if(n % 2 == 1){
		int l = fib(n / 2), r = fib((n / 2) + 1);
		return a[n] = (l * l + r * r) % mod;
	}
	else return a[n] = fib(n / 2) * (fib((n / 2) - 1) + fib((n / 2) + 1)) % mod;
}
signed main(){
    a[2] = a[1] = 1;
	long long n, m;
	cin >> n >> m;
	cout << fib(__gcd(n, m));

	return 0;
}

时间复杂度：$O(\log^2n)$.