【斐波那契】【矩阵快速幂模板】斐波那契公约数

绝地灬酷狼 2023-06-01 08:46 18阅读 0赞

这道题求第n项和第m项斐波那契的公约数这里有一个定理（n，m都是1e9）

gcd(f\[m\],f\[n\])=f\[gcd(n,m)\]

斐波那契使用矩阵快速幂求

#include <bits/stdc++.h>
    #define ll long long
    #define ull unsigned long long
    #define ld long double
    using namespace std;
    const int maxn=20010;
    const int NIL=0;
    const int mod=100000000;
    ll n,m;
    struct node
    {
        ll a[3][3];
        ll x,y;
    };
    inline node mul(node a,node b)
    {
        node tmp;
        memset(&tmp,0,sizeof(tmp));
        for(int i=0;i<a.x;i++)
        {
            for(int j=0;j<b.y;j++)
            {
                for(int k=0;k<a.y;k++)
                {
                    tmp.a[i][j]=(tmp.a[i][j]+a.a[i][k]*b.a[k][j]%mod)%mod;
                }
            }
        }
        tmp.x=a.x;
        tmp.y=b.y;
        return tmp;
    }
    ll qm(ll b)
    {
        node ant,tmp;
        memset(&tmp,0,sizeof tmp);
        memset(&ant,0,sizeof ant);
        tmp.x=2;
        tmp.y=2;
        tmp.a[0][0]=tmp.a[0][1]=tmp.a[1][0]=1;
        ant.x=1;
        ant.y=2;
        ant.a[0][0]=ant.a[0][1]=1;
        while(b)
        {
            if(b&1)
                ant=mul(ant,tmp);
            tmp=mul(tmp,tmp);
            b>>=1;
        }
        return ant.a[0][0];
    }
    ll gcd(ll a,ll b)
    {
        if(b==0)
            return a;
        return gcd(b,a%b);
    }
    int main()
    {
        scanf("%lld %lld",&n,&m);
        n=gcd(n,m);
        if(n<=2)
            printf("1\n");
        else
            printf("%lld\n",qm(n-2));
        return 0;
    }

转载于:https://www.cnblogs.com/Diliiiii/p/11232535.html

发表评论取消回复

表情：

评论列表（有 0 条评论，18人围观）

还没有评论，来说两句吧...

相关阅读

相关【斐波那契】【矩阵快速幂模板】斐波那契公约数

这道题求第n项和第m项斐波那契的公约数这里有一个定理（n，m都是1e9） gcd(f\[m\],f\[n\])=f\[gcd(n,m)\] 斐波那契使用矩阵快速幂求

绝地灬酷狼/ 2023年06月01日 08:46/ 0 赞/ 19 阅读

相关【模板】【矩阵快速幂】求第n项斐波那契

注意a数组初始化，调用Pow（a，n，w），n是第几项，求斐波那契中w默认为2 ll tmp[2][2],res[2][2]; void multi(ll a

深藏阁楼爱情的钟/ 2023年06月01日 08:46/ 0 赞/ 13 阅读

相关斐波那契数列

关于斐波那契数列的解法，本人找到了一种比较简单的方法，结果是正确的，不知道各位有没有另外更好的解法，一起探讨探讨。 import java.util.; pu

╰+攻爆jí腚メ/ 2022年08月01日 12:15/ 0 赞/ 370 阅读

相关斐波那契数列

定义：斐波那契数列指的是这样一个数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … 这个数列从第三项开始，每一项都等于前两项之和。

矫情吗；*/ 2022年07月13日 04:49/ 0 赞/ 316 阅读

相关斐波那契数列

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，

冷不防/ 2022年07月13日 03:19/ 0 赞/ 341 阅读

相关斐波那契数列

class FibIter(object): def __init__(self, lenth): self.lent

一时失言乱红尘/ 2022年05月27日 13:51/ 0 赞/ 341 阅读

相关斐波那契数列

include<iostream> using namespace std; int fibonacci1(int t) { if(t

古城微笑少年丶/ 2022年05月09日 08:58/ 0 赞/ 304 阅读

相关斐波那契查找

1. 问题描述我们知道，对于有序数据序列进行查找，二分查找法性能是相当好的，时间效率达到O(log2n)，但该算法其实还有些可以进行改进的地方。普通的折半查找直接通过折

Bertha 。/ 2022年03月28日 10:46/ 0 赞/ 323 阅读

相关斐波那契博弈

一堆个数为n的物品，双方轮流按如下规则取物品，取完最后物品的人胜利。先手不可以第一次取完所有物品。之后每次可以取得物品个数1<=k<=对手上次取得个数的2倍。

阳光穿透心脏的1/2处/ 2021年12月24日 13:51/ 0 赞/ 188 阅读

相关斐波那契查找

Introduce 黄金分割查找，区别于插值查找找0.5，斐波那契查找找0.618。 ![18721752-80ed4220f6009617.png][]

野性酷女/ 2021年09月30日 08:46/ 0 赞/ 431 阅读