UVA 11582 Colossal Fibonacci Numbers! 大斐波那契数

大致题意：输入两个非负整数a,b和正整数n。计算f(a^b)%n。其中f[0]=f[1]=1, f[i+2]=f[i+1]+f[i]. 即计算大斐波那契数再取模。

一开始看到大斐波那契数，就想到了矩阵快速幂，输出等了几秒钟才输出完，肯定会超时。因为所有计算都是要取模的，设F[i]=f[i] mod n。F[0]=F[1]=1。只要出现F[i]=F[i+1]=1，那么整个序列就会重复。例如n=3，则序列为1，1，2，0，2，2，1，0，1，1……第九项和第十项都等于1，所以之后的序列都会重复。

至于多久会重复一次，这个没法直接看出来。我的程序是一直判断下去知道有相邻地两个1，这样有点冒险，不过没有超时。后来看了下刘汝佳的书，书上这样说的：因为余数最多n种，所以最多n²项就会重复。这是一个结论吗，我没看懂，先记着吧。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int maxn=+;

typedef unsigned long long ull;

int modnum[maxn];

int Mod;

int powermod(ull a,ull b,int c)

{

    ull ans=;

    a%=c;

    while(b)

    {

        if(b&)

           ans=ans*a%c;

        a=a*a%c;

        b=b>>;

    }

    return ans;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int t;

    ull a,b;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%llu%llu%d",&a,&b,&Mod);

        if(Mod== || a==)

        {

            printf("0\n");

            continue;

        }

        modnum[]=modnum[]=;

        int p=;

        for(int i=;;i++)

        {

            modnum[i]=(modnum[i-]+modnum[i-])%Mod;

            if(modnum[i]== && modnum[i-]==)

            {

                p=i-;

                break;

            }

        }

        printf("%d\n",modnum[powermod(a,b,p)-]);

    }

    return ;

}

UVA 11582 Colossal Fibonacci Numbers! 大斐波那契数的相关教程结束。