烦神的斐波那契&&洛谷-1306-斐波那契公约数

时间：2023-03-08 21:13:56

传送门

洛谷1306传送门

-----------------------------------------------------------------------------------------------------------------------------------------------------

内网题题面

题目描述

烦神看上了一个妹子，烦神想找她约会，可是妹子出了一道数学题来考验烦神，烦神只有做对了，妹子才会跟他去约会，题目是这样的：

给出两个正整数A和B，要求求出斐波那契数列的第A项和第B项的最大公约数，结果对19990208取模（烦神约的妹子的生日）。

烦神当然可以秒杀啦，但是他没有时间做，于是他把这个问题留给了你们，他还要节省下时间去约下一个妹子，你能帮帮他吗?

输入

第一行一个正整数T，表示有T组数据,

接下来T行，每行两个正整数A和B。

输出

输出有T行，第 i 行对应第 i 组数据的答案.

样例输入

2

1 1

36 48

样例输出

1

144

提示

0 < A, B <= 10^9.

1 <= T <= 100000.

-----------------------------------------------------------------------------------------------------------------------------------------------------

有一个很有意思的点

　　　　gcd(F[n],F[m])=F[gcd(n,m)]

于是再+矩阵快速幂就好了

#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[][],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()

{

    ios::sync_with_stdio();

    cin>>n>>m;

    n=gcd(n,m);

    if(n<=)cout<<;

    else fast(n-);

    return ;

}
#include<cstdio>

#include<algorithm>

#include<cstring>

#define ll long long

using namespace std;

const ll mod = ;

ll u,f[];

struct mat

{

    ll m[][],l,r;

};

inline mat mul(mat x,mat y)

{

    mat p;

    memset(&p,,sizeof(p));

    for(int i = ;i <= x.l;i++)

        for(int j = ;j <= y.r;j++)

            for(int k = ;k <= x.r;k++)

                p.m[i][j] = (p.m[i][j] + x.m[i][k] *y.m[k][j]%mod)% mod;

    p.l = x.l,p.r = y.r;

    return p;

}

void fast(ll k)

{

    mat p,ans;

    memset(&p,,sizeof(p));

    memset(&ans,,sizeof(ans));

    p.m[][] = p.m[][] = p.m[][] = ;

    p.l = ;p.r = ;

    ans.m[][] = ans.m[][] = ;

    ans.l = ,ans.r = ;

    while(k)

    {

        if(k & )

            ans = mul(ans,p);

        p = mul(p,p);

        k >>= ;

    }

    printf("%lld\n",ans.m[][]);

}

int main()

{

    int t;

    scanf("%d",&t);

    ll a,b,maxn = -;

    f[] = f[] = ;

    for(int i = ;i <= t;i++)

    {

        scanf("%lld%lld",&a,&b);

        u = __gcd(a,b);

        if(u <= )

            printf("1\n");

        else

            fast(u - );

    }

    return ;

}

emm...

两次都因为struct结构体后面忘加“；”而gg

好在

还是一次a了

相关文章