wyh的数列快速幂+循环节+ull的用法

最新推荐文章于 2020-11-29 05:42:20 发布

keepcoral

最新推荐文章于 2020-11-29 05:42:20 发布

阅读量265

点赞数

分类专栏：快速幂循环节

本文链接：https://blog.csdn.net/keepcoral/article/details/79829268

版权

快速幂同时被 2 个专栏收录

3 篇文章

订阅专栏

循环节

1 篇文章

订阅专栏

本文介绍了一个关于求解斐波那契数列中特定项对某个数取余的问题，通过寻找循环节并利用快速幂运算来解决大数问题。提供了完整的C++代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

链接： https://www.nowcoder.com/acm/contest/93/K
来源：牛客网

题目描述

wyh学长特别喜欢斐波那契数列，F（0）=0，F（1）=1，F（n)=F(n-1)+F(n-2)(n>=2)

一天他突发奇想，想求F（a^b）%c

输入描述:

输入第一行一个整数T(1<=T<=100)，代表测试组数
接下来T行，每行三个数 a,b,c (a,b<=2^64) (1<c<1000)

输出描述:

输出第a^b项斐波那契数对c取余的结果

示例1

输入

3
1 1 2
2 3 1000
32122142412412142 124124124412124 123

输出

1
21
3

这题目很坑，数据输入要用llu，unsigned long long ，找到循环节，然后快速幂就可以求解了

循环节应用f[i-1]==0&&f[i]==1，那么到达i-1就是循环节，也就是循环长度

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef unsigned long long LL;
LL t,a,b,c,xun;
LL quickk(LL a,LL b)
{
    LL ans=1;
    a=a%xun;
    while(b>0)
    {
        if(b&1)
        {
            ans=(ans*a)%xun;
        }
        b>>=1;
        a=(a*a)%xun;
    }
    return ans;
}
LL f[1000100];
int main()
{
    LL t;
    scanf("%lld",&t);
    while(t--)
    {
        int i;
        f[0]=0;
        f[1]=1;
        scanf("%llu%llu%llu",&a,&b,&c);
        for(i=2; i<=1000100; i++)
        {
            f[i]=(f[i-1]+f[i-2])%c;
            if(f[i-1]==0&&f[i]==1)
            {
                 xun=i-1;
                break;
            }
        }
        printf("%llu\n",f[quickk(a,b)]);
    }
    return 0;
}