自动搬运

查看原文

来自洛谷，原作者为

	浅色调 **

搬运于2025-08-24 21:23:34，当前版本为作者最后更新于2018-04-03 15:39:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

本题其实并不难，开始被题意吓到了，结果后面写出了式子都没看出来（手动滑稽～）。 发现自己推结论的方法不太一样，所以发发题解。

$\quad$方法：结论+矩阵加速

$\quad$结论：$$gcd(F[n],F[m])=F[gcd(n,m)]$$

$\quad$证明：

我们设$n<m$，$F[n]=a$和$F[n+1]=b$。

则$F[n+2]=a+b,F[n+3]=a+2b,…F[m]=F[m-n-1]a+F[m-n]b$

$\because \quad$ $F[n]=a,F[n+1]=b,F[m]=F[m-n-1]a+F[m-n]b$

$\therefore \quad$ $F[m]=F[m-n-1]*F[n]+F[m-n]*F[n+1]$

又$\because \quad$ $gcd(F[n],F[m])=gcd(F[n],F[m-n-1]*F[n]+F[m-n]*F[n+1])$

而$F[n]|F[m-n-1]*F[n]$

$\therefore \quad$ $gcd(F[n],F[m])=gcd(F[n],F[m-n]*F[n+1])$

引理：$gcd(F[n],F[n+1])=1$

证：由欧几里德定理知

$gcd(F[n],F[n+1])=gcd(F[n],F[n+1]-F[n])=gcd(F[n],F[n-1])$

$=gcd(F[n-2],F[n-1])$

$……$

$=gcd(F[1],F[2])=1$

$\therefore \quad$ $gcd(F[n],F[n+1])=1$

由引理知：

$F[n],F[n+1]$互质

而$gcd(F[n],F[m])=gcd(F[n],F[m-n]*F[n+1])$

$\therefore \quad$ $gcd(F[n],F[m])=gcd(F[n],F[m-n])$

即$gcd(F[n],F[m])=gcd(F[n],F[m\;mod\;n])$

继续递归，将$m1=m\;mod\;n$，则$gcd(F[n],F[m])=gcd(F[n\;mod\;m1],F[m1])$

$…$

不难发现，整个递归过程其实就是在求解$gcd(n,m)$

最后递归到出现$F[0]$时，此时的$F[n]$就是所求gcd。

$$\therefore \quad gcd(F[n],F[m])=F[gcd(n,m)]$$

于是本题就转为求$gcd(n,m)$，然后求斐波拉契数列的$F[gcd(n,m)]$项后8位（即对100000000取模）。

至于矩阵的构造：

初始矩阵 $\begin{bmatrix} F[2]=1 & F[1]=1\end{bmatrix}$

以及中间矩阵 $\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

注意矩阵数组开long long！！

$\quad$欢迎来踩博客（转载请注明出处）：five20

代码：

// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define il inline
#define ll long long
#define mem(p) memset(&p,0,sizeof(p))
using namespace std;
const ll mod=1e8;
ll n,m;
struct mat{ll a[3][3],r,c;};
il mat mul(mat x,mat y)
{
	mat p;
	mem(p);
	for(int i=0;i<x.r;i++)
		for(int j=0;j<y.c;j++)
			for(int k=0;k<x.c;k++)
	p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j])%mod;
	p.r=x.r,p.c=y.c;
	return p;
}
il void fast(ll k)
{
	mat p,ans;
	mem(p),mem(ans);
	p.r=p.c=2;
	p.a[0][0]=p.a[0][1]=p.a[1][0]=1;
	ans.r=1,ans.c=2;
	ans.a[0][0]=ans.a[0][1]=1;
	while(k)
	{
		if(k&1)ans=mul(ans,p);
		p=mul(p,p);
		k>>=1;
	}
	cout<<ans.a[0][0];
}
il ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	n=gcd(n,m);
	if(n<=2)cout<<1;
	else fast(n-2);
	return 0;
}