洛谷 P1306 斐波那契公约数

题目描述

对于Fibonacci数列:1,1,2,3,5,8,13......大家应该很熟悉吧~~~但是现在有一个很“简单”问题:第n项和第m项的最大公约数是多少?

Update:加入了一组数据。

输入输出格式

输入格式:

两个正整数n和m。(n,m<=10^9)

注意:数据很大

输出格式:

Fn和Fm的最大公约数。

由于看了大数字就头晕,所以只要输出最后的8位数字就可以了。

输入输出样例

输入样例#1: 

4 7
输出样例#1: 

1

说明

用递归&递推会超时

用通项公式也会超时

题解:

emmmm,这题,我差不多错了十三四遍吧。

真是有成就感。

80分代码:

 #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
ll n,m;
ll gcd(ll a,ll b){
if(b==)return a;
return gcd(b,a%b);
}
ll a[];
int main(){
scanf("%lld %lld",&n,&m);
ll w=gcd(n,m);
a[]=;
a[]=;
for(int i=;i<=w;i++)
a[i]=(a[i-]+a[i-])%;
printf("%lld",a[w]);
return ;
}

AC

#include<cstdio>
#include<iostream>
#include<cstring>
#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[][],r,c;
};
il mat mul(mat x,mat y) {
mat p;
mem(p);
for(int i=; i<x.r; i++)
for(int j=; j<y.c; j++)
for(int k=; 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=;
p.a[][]=p.a[][]=p.a[][]=;
ans.r=,ans.c=;
ans.a[][]=ans.a[][]=;
while(k) {
if(k&)ans=mul(ans,p);
p=mul(p,p);
k>>=;
}
cout<<ans.a[][];
}
il ll gcd(ll a,ll b) {
return b?gcd(b,a%b):a;
}
int main() {
cin>>n>>m;
n=gcd(n,m);
if(n<=)cout<<;
else fast(n-);
return ;
}

一世安宁

05-11 22:15