P1306 斐波那契公约数

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=10000010;
const int mod=1e8;

long long n,m;

struct no {
	long long a[3][3];
	long long r,c;
};

no mul(no x,no y) {
	no p;
	memset(&p,0,sizeof(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;
}

void fast(long long k) {
	no p,ans;
	memset(&p,0,sizeof(p));
	memset(&ans,0,sizeof(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;
	}
	printf("%lld\n",ans.a[0][0]);
}

long long gcd(long long a,long long b) {
	if(a<b)
		swap(a,b);
	if(a%b==0)
		return b;
	else
		return gcd(b,a%b);
}

int main() {
	scanf("%lld%lld",&n,&m);
	n=gcd(n,m);
	if(n<=2)
		printf("1\n");
	else
		fast(n-2);
	return 0;
}