题目:斐波那契公约数

问题编号:294

题目描述

对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在hanzhoufeng有一个很“简单”问题：第n项和第m项的最大公约数是多少？但是hanzhoufeng数学太烂了，只好去问上任数学课代表么么虫....但是么么虫也不会，只好来请教你了......

输入格式

两个正整数n和m。（n,m<=10^9）

输出格式

Fn和Fm的最大公约数。
由于hanzhoufeng看了大数字就头晕，所以只要输出最后的8位数字就可以了。

样例输入

4 7

样例输出

1

平时很少逛OI的网站。今天去瞧了瞧，看了下这个题

很久以前在具体数学上面看到过这个公式

gcd(fn,fm)=f(gcd(n,m))

所以求出n和m的最大公约数，然后矩阵二分幂就可以搞定了

这个题要用__int64

然后就是那个输出的前导零比较恶心，因为题目没有说

我的代码：

#include<stdio.h>
#include<algorithm>
#include<string.h>

using namespace std;

struct mart{
	__int64 mat[3][3];
};
__int64 mod=100000000;
mart kk;

__int64 gcd(__int64 a,__int64 b){
	if(b==0)
		return a;
	else
		return gcd(b,a%b);
}

mart multi(mart a,mart b){
	mart c;
	__int64 i,j,k;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			c.mat[i][j]=0;
			for(k=1;k<=2;k++)
				c.mat[i][j]=(c.mat[i][j]%mod+(a.mat[i][k]%mod)*(b.mat[k][j]%mod)%mod)%mod;
		}
	return c;
}

mart power(__int64 k){
	mart p,q;
	__int64 i,j;
	for(i=1;i<=2;i++)
		for(j=1;j<=2;j++)
		{
			p.mat[i][j]=kk.mat[i][j];
			if(i==j)
				q.mat[i][j]=1;
			else
				q.mat[i][j]=0;
		}
	if(k==0)
		return q;
	while(k!=1)
	{
		if(k&1)
		{
			k--;
			q=multi(p,q);
		}
		else
		{
			k=k>>1;
			p=multi(p,p);
		}
	}
	p=multi(p,q);
	return p;
}

int main(){
	__int64 n,m,k;
	mart xx;
	while(scanf("%I64d%I64d",&n,&m)!=EOF)
	{
		k=gcd(n,m);
		kk.mat[1][1]=0;
		kk.mat[1][2]=1;
		kk.mat[2][1]=1;
		kk.mat[2][2]=1;
		xx=power(k-1);
		if(k>10)
			printf("%08I64d\n",(xx.mat[1][1]+xx.mat[1][2])%mod,(xx.mat[2][1]+xx.mat[2][2])%mod);
		else
			printf("%I64d\n",(xx.mat[1][1]+xx.mat[1][2])%mod,(xx.mat[2][1]+xx.mat[2][2])%mod);
	}
	return 0;
}