洛谷 P1306 斐波那契公约数

　　　　　　　　　　　　　　　　　　　　　　　　　洛谷 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：

说明

用递归&递推会超时

用通项公式也会超时

题解：

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

真是有成就感。

80分代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 #define ll long long
 4 using namespace std;
 5 ll n,m;
 6 ll gcd(ll a,ll b){
 7     if(b==0)return a;
 8     return gcd(b,a%b);
 9 }
10 ll a[10000001];
11 int main(){
12     scanf("%lld %lld",&n,&m);
13     ll w=gcd(n,m);
14     a[1]=1;
15     a[2]=1;
16     for(int i=3;i<=w;i++)
17         a[i]=(a[i-1]+a[i-2])%100000000;
18     printf("%lld",a[w]);
19     return 0;
20 }

View Code

#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[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() {
    cin>>n>>m;
    n=gcd(n,m);
    if(n<=2)cout<<1;
    else fast(n-2);
    return 0;
}

View Code

一世安宁